Civilization 5 Mod validator part 2

Question

Here is another portion of the same program that I would like optimizing (85-95% of the time running the program is spent within this class!!!) so that it runs faster, especially for users who have less powerful computers.

Any optimizations for this section of the code would be greatly appreciated! I have done my best again to comment my code to help you understand it and I will post a short paragraph introducing the data system. Please note, that although I acknowledge that using braces on the same like as the statement is convention, I find it very hard to read code in this form and so I use the brace on the next line style!

As promised here is the way the data is stored:

Table class contains a HashMap of Table instances paired with their name, which are accessed by getTable(String name) or getRegister() for everything

A Table contains a HashMap <String, Vector<Row>> which stores Rows, grouped by their primary tag's name (which is the tag that they define, if they don't define a tag their name is "")

a Row contains an LinkedHashMap of Tag <?>s which can be varying types such as int or String mapped to their name.

The Tag has a name and a ? data field.

and the code in question:

public class ReferenceDetector
{
    private HashMap<String, Table> register; //a variable which contains all the data

    public ReferenceDetector(HashMap<String, Table> register)
    {
        this.register = register;
    }

    /*
     * Here our main job is to find any tags in the register that:
     *  contain a body of a String
     *  is not excluded by the program as an ignored tag
     * and check to see if they are defined as existing in the primary tables
     */
    void findReferences(boolean store)
    {
        Table dump = new Table("Dump", true, true); //the dump table is used to define any references that are errors in the Base Game, 
                                                    //they clearly work so the mod should be able to use them! (typically these references exist in the DLL or Lua
        for (Table table : register.values()) // for every table in the register
        {
            for (ArrayList<Row> rowReferences : table.getRows().values()) //for every group of same named rows in the table
            {
                for (Row row : rowReferences) // for every row in this group
                {
                    for (Tag<?> tag : row.getTags())  // for every tag in this row
                    {
                        if (tag.get() instanceof String && !Excludes.checkExcludedTag((String) tag.get())) // are we a String and not to be ignored?
                        {
                            String tableTarget = determineTable(tag.getName()); //determine the table name (see below)
                            // attempt to resolve the reference, to check if it was defined, so if we have the tag CIVILIZATION_NEPAL, does it exist in the primary table Civilizations?
                            // the boolean argument for resolveReference is used in case of no found table!
                            boolean passed = !tableTarget.equals("") ? resolveReference(new Reference(tableTarget, (String) tag.get()), false) : resolveReference(new Reference(tableTarget, (String) tag.get()), true);
                            if (!passed && !store) // we didn't succeed and we are not checking the base game
                            {
                                System.out.println(String.format("MISSING REFERENCE: %s %sin %s references %s in tag %s, this object doesn't exist"
                                        , !row.getIdentifier().isEmpty() ? "Row with type" : String.format("Entry with %s = %s", row.getTags().toArray(new Tag<?> [] {})[0].getName(), row.getTags().toArray(new Tag<?> [] {})[0].get())        
                                                , !row.getIdentifier().isEmpty() ? row.getIdentifier() + " " : ""
                                                    , table.getIdentifier()
                                                    , tag.get()
                                                    , tag.getName())); //print out the diagnosis to the user
                            }
                            else if (!passed && store) // if we are checking the base game, no body cares about this error! Just a DLL definition, just create the definition in the dump so that it can be used by mods
                            {
                                dump.addDumpRow((String) tag.get());
                            }
                        }
                    }
                }
            }
        }
        dump.register(); //add the dump table to the register itself!
    }

    /*
     * Let's run through the targetTable, or the whole register (if bruteForce is true) for this tag's definition
     * a Reference simply contains the targetTable name (or null) and the actual tag we are looking for (as object)
     */
    boolean resolveReference(Reference ref, boolean bruteForce)
    {
        boolean regexSearch = ref.object.contains("%");
        /*
         * The above line is important.
         * Some tags represent text, and in-game any random dialog or stuff used in the in-game pedia is written in this form:
         * TXT_KEY_..._n (where n represents the variants so 1, 2, 3, 4 etc)
         * Then in the xml, where they are needed the code is instructed to accept anything with the form TXT_KEY_..._% to denote any of these tags
         * hence why we need to do the same! if there is a % chances are it could be defined as something slightly different! 
         */
        Pattern search = Pattern.compile(ref.object.replace(".", "\\.").replace("%", ".+")); //convert any . into regex literals, and convert the % into a regex of: any character at least once (for times when we are looking in the dump)

        if (!bruteForce && register.get(ref.targetTable).getRows().containsKey(ref.object)) { return true; } // we looked in the targetTable and found the definition, success!
        else // looks like we need to go through everything... (from bruteForce or unable to find in the targetTable)
        {
            for (Table table : register.values()) //for every table
            {
                if (table.isPrimary()) //if it is primary (definitions of keys are only ever primary)
                {
                    if (regexSearch) //if we detect the use of %
                    {
                        for (String key : table.getRows().keySet()) //for every row group name
                        {
                            if (search.matcher(key).matches()) //if this matches, the primary key is the one we were looking for!
                            {
                                return true;
                            }
                        }
                    }
                    else
                    {
                        if (table.getRows().containsKey(ref.object)) // is the key we are looking for the name of a row group (if it is, then we know it is a primary key definition)
                        {
                            return true;
                        }
                    }
                }
            }
            return false;
        }
    }

    String determineTable(String tagName)
    {
        // Try to identify the table based on Convention 
        if (tagName.contains("Type") && register.containsKey(tagName.substring(0, tagName.length() - 4) + "s")) //are we of the form ____Type ? if so then cut off the Type and add s, this usually is another table
        {
            if (Table.getTable(tagName.substring(0, tagName.length() - 4) + "s").isPrimary()) // is the table that we have found primary (and therefore defines the reference)
            {
                return tagName.substring(0, tagName.length() - 4) + "s"; // yes, let's assume it is the right table!
            }
        }
        // We failed... send notice for brute force
        return "";
    }

    private class Reference
    {
        private String targetTable, object;

        Reference(String targetTable, String object)
        {
            this.targetTable = targetTable;
            this.object = object;
        }
    }
}

Also, here is a quick overview of what the code has to achieve and some background:

This part of the program is responsible for ensuring that any tags that are defined in the mods do actually exist somewhere else in the mod/any dependency mods/the base game itself.

For example, my mod has a tag which says that England's unique unit should be UNIT_LONGBOWMAN. This code will then check that UNIT_LONGBOWMAN does in fact exist. It first attempts to work out the table where it might have been defined (The tag itself exists like this in xml: <UnitType>UNIT_LONGBOWMAN</UnitType>, we should take UnitType->Unit->Units as our table name) and then searches there (if it actually is a table known by that name) for a row which has an identifier that matches this tag content (which indicates that row is responsible for defining UNIT_LONGBOWMAN, otherwise it's name would be ""). If it couldn't find a table that could contain the definition, it performs brute force and checks every table in the data for a row group that defines this tag!

If you have any questions do not hesitate to ask!

EDIT (for Table class + children):

public class Table implements Serializable //the register is serialised to be used next runtime, easier that way :)
{
    private static final long serialVersionUID = 1L;
    private boolean primary;
    private boolean nonUnique = false;

    private static HashMap<String, Table> register = new HashMap<String, Table> ();

    private HashMap<String, ArrayList<Row>> rows = new HashMap<String, ArrayList<Row>> ();
    private String tableIdentifier;

    public static HashMap<String, Table> getRegister() { return register; }
    public boolean isPrimary() { return primary; }
    public void setIsPrimary(boolean value) { primary = value; }
    public boolean isNonUnique() { return nonUnique; }
    public void setIsNonUnique(boolean value) { nonUnique = value; }

    // Constructor called from Table.getTable(String)
    private Table(String identifier, boolean primary)
    {
        tableIdentifier = identifier;
        this.primary = primary;
        register();
    }

    // Called where ever we need to create a table but not register it!
    public Table(String identifier, boolean primary, boolean preprepare)
    {
        tableIdentifier = identifier;
        this.primary = primary;
    }

    public void register()
    {
        register.put(tableIdentifier, this);
    }

    public String getIdentifier() { return tableIdentifier; }

    // get or define and get a table
    public static Table getTable(String identifier)
    {
        return getRegister().containsKey(identifier) ? getRegister().get(identifier) : new Table(identifier, MainLauncher.reader.isPrimaryTable(identifier));
    }

    public ArrayList<Row> getRows(String identifier)
    {
        return rows.get(identifier);
    }

    public HashMap<String, ArrayList<Row>> getRowGroups() { return rows; }

    // add row to this table, then return it (or return the any row that is identical in contents and name)
    public Row addRow(Row row, boolean ignore)
    {
        String rowIdentifier = row.getIdentifier();
        if (!rows.containsKey(rowIdentifier)) rows.put(rowIdentifier, new ArrayList<Row> ());
        if (!primary || nonUnique) 
        {
            if (rows.get(rowIdentifier).isEmpty())
            {
                rows.get(rowIdentifier).add(row);
            }
            else
            {
                out: for (Row loopRow : rows.get(rowIdentifier))
                {
                    for (Tag<?> loopTag : loopRow.getTags())
                    {
                        if (row.getTag(loopTag.getName()) == null || (!row.getTag(loopTag.getName()).get().equals(loopTag.get())))
                        {
                            rows.get(rowIdentifier).add(row);
                            break out;
                        }
                    }
                    return loopRow;
                }
            }
        }
        else
        {
            if (!rows.get(rowIdentifier).isEmpty())
            {
                rows.get(rowIdentifier).clear();
                if (!ignore) System.out.println(String.format("WARNING: Cannot have more than one of same type: %s in %s", rowIdentifier, tableIdentifier));
            }
            rows.get(rowIdentifier).add(row);
        }
        return row;
    }

    // used for dumping base game problems
    public void addDumpRow(String identifier)
    {
        if (!rows.containsKey(identifier)) rows.put(identifier, new ArrayList<Row> ());
        if (!rows.get(identifier).isEmpty())
        {
            rows.get(identifier).clear();
        }
        rows.get(identifier).add(new Row(identifier));
    }

    // called from the XML readers, if the delete tag was identified. just removes rows from the table that have tables that match all "wheres"
    public <T> void deleteRow(HashMap<String, T> wheres)
    {
        HashMap<String, Vector<Row>> deletes = new HashMap<String, Vector<Row>> ();
        for (String rowName : rows.keySet())
        {
            for (Row row : rows.get(rowName))   
            {
                boolean matches = true;
                for (String identifier : wheres.keySet())
                {
                    T content = wheres.get(identifier);
                    if (row.getTags().stream().anyMatch(tag -> !tag.get().equals(content) && tag.getName().equals(identifier)))
                    {
                        matches = false;
                        break;
                    }
                }
                if (matches)
                {
                    if (!deletes.containsKey(rowName))
                    {
                        deletes.put(rowName, new Vector<Row> ());
                    }
                    deletes.get(rowName).add(row);
                }
            }
        }

        for (String name : deletes.keySet())
        {
            ArrayList<Row> group = rows.get(name);
            deletes.get(name).stream().forEach(group::remove);
            if (group.isEmpty()) rows.remove(name);
        }
    }

    // similar to deleteRow(), replaces the contents of any rows that match all wheres with the updates
    public <T, U> void updateRow(HashMap<String, T> wheres, HashMap<String, U> updates)
    {
        for (ArrayList<Row> rowGroup : rows.values())
        {
            for (Row row : rowGroup)
            {
                Vector<String> updatesToApply = new Vector<String> ();
                boolean matches = false;
                for (Tag<?> tag : row.getTags())
                {
                    matches = true;
                    if (wheres.keySet().stream().anyMatch(tagName -> !tag.getName().equals(tagName) || !tag.get().equals(wheres.get(tagName))))
                    {
                        matches = false;
                        break;
                    }

                    if (matches)
                    {
                        updates.keySet().stream().forEach(updatesToApply::add);
                    }
                }

                for (String updateName : updatesToApply)    
                {
                    if (row.getTag(updateName) != null)
                    {
                        row.removeTag(row.getTag(updateName));
                    }
                    row.addTag(updateName, new Tag<U>(updateName, updates.get(updateName)));
                }
            }
        }
    }

    public static class Row implements Serializable
    {
        private static final long serialVersionUID = 1L;

        private String rowIdentifier;
        private LinkedHashMap<String, Tag<?>> tags;

        Row(String identifier)
        {
            tags = new LinkedHashMap<String, Tag<?>> ();
            rowIdentifier = identifier;
        }

        public void removeTag(Tag<?> tag)
        {
            tags.remove(tag.getName());
        }

        public void addTag(String identifier, Tag<?> tag)
        {
            tags.put(identifier, tag);
        }

        public Tag<?> getTag(String identifier) { return tags.get(identifier); }
        public Collection<Tag<?>> getTags() { return tags.values(); }

        public String getIdentifier() { return rowIdentifier; }

        public static class Tag<T> implements Serializable
        {
            private static final long serialVersionUID = 1L;

            private T data;
            private String tagIdentifier;

            Tag(String identifier, T data)
            {
                tagIdentifier = identifier;
                this.data = data;
            }

            public T get() { return data; }
            public String getName() { return tagIdentifier; }

        }
    }
}

Answer 1

Without the full program, I can't profile runs to prove where issues are and that my suggestions will improve them, so I'm guessing a bit. Further, I have no knowledge of Civilization 5's file structure so please gloss over misuse of terms. That said, I do have some suggestions and an angle or two to explore.

---

boolean resolveReference(Reference ref, boolean bruteForce)

You're basically doing a full scan over all of your data when you resort to brute force. For a bit more memory use, you can build an index to help speed things up. To do this, you'll need to make your HashMap<String, Table> register a first-class citizen by giving it its own class, Register.

For brevity, I'm going to use the Multimap from the guava libraries. It feels like it will make a difference here.

// Register.java
public class Register {
  private static final Register global = new Register();
  public static Register global() {
    return global;
  }

  SetMultimap<String, Table> keysToTable = HashMultimap.create();
  Map<String, Table> tablesByName = new HashMap<>();

  public boolean resolveReference(Reference ref) {
    return keysToTable.containsKey(ref.object);
  }

  public Table getOrCreateTable(String name) {
    Table table = tablesByName.get(name);
    if ( table == null ) {
      table = new Table(name);
      tablesByName.put(name, table);
    }
    return table;
  }

  static <V> void addPrefixes(String key, V value, Multimap<String, V> multimap) {
    for (int end = key.length(); end >= 0; end-- ) {
      multimap.put(key.substring(0, end) + "%", value);
    }
  }

  public class Table {
    String name;
    ListMultimap<String, Row> rowsByPrimaryTag = ArrayListMultimap.create();

    Table(String name) {
      this.name = name;
    }

    public void addRow(String key, Row row) {
      keysToTable.put(key, this);
      addPrefixes(key, this, keysToTable);

      // add to rowsByPrimaryTag as needed
    }

    public Register getRegister() {
      return Register.this;
    }
  }
}

addPrefixes assumes that the % expansion wildcard only happens at the very end of a specifier. The method could be made to account for other uses, if necessary. What it does is basically:

addPrefixes("ARCHER", table, mm) {
  mm.put("ARCHER%", table)
  mm.put("ARCHE%", table)
  mm.put("ARCH%", table)
  mm.put("ARC%", table)
  mm.put("AR%", table)
  mm.put("A%", table)
  mm.put("%", table)
}

So that, if you later add a key "ARCHON" to another table (or the same), "ARCH%" will find both tables immediately. That should take care of the brute force issues and remove the need for regexes, I think.

---

String determineTable(String tagName)

The expression tagName.substring(0, tagName.length() - 4) + "s" appears often in here. Consider extracting it and replacing it with a local final variable:

String determineTable(String tagName) {
    // unit_type -> units
    final String tableName = tagName.substring(0, tagName.length() - 4) + "s";
    // Try to identify the table based on Convention 
    if (tagName.contains("Type") && register.containsKey(tableName)) { //are we of the form ____Type ? if so then cut off the Type and add s, this usually is another table
        if (Table.getTable(tableName).isPrimary()) { // is the table that we have found primary (and therefore defines the reference)
            return tableName; // yes, let's assume it is the right table!
        }
    }
    // We failed... send notice for brute force
    return "";
}

It will shave off a few operations, and improve the method's robustness to change.

---

private class Reference

Do you need this one? Since the class holds no logic, only data, and sees use only once, maybe it's better to flatten it out:

   public boolean resolveReference(Reference ref)
-> public boolean resolveReference(String object, String targetTable)

Removes some allocations and field lookups. That's slim pickings, though: if you do use it elsewhere, or you feel it makes things less readable, or you intend to flesh it out later, just leave it be.

---

void findReferences(boolean store)

boolean passed = !tableTarget.equals("") ?
        resolveReference(new Reference(tableTarget, (String) tag.get()), false) :
        resolveReference(new Reference(tableTarget, (String) tag.get()), true);

can be shortened to:

boolean passed = resolveReference(
        new Reference(tableTarget, (String) tag.get()),
        tableTarget.equals(""));

---

On a stylistic note, your code feels overdocumented. You did provide useful comments (pointing out special casing on '%', for instance), but some lines were superfluous, like on the iteration in findReferences.

Aim for self-documenting code through the naming of variables, classes, and methods. If that's not enough, add javadoc to the methods or fields troubling you.

String guessTableName(String tagName) {
    if ( tagName.endsWith("Type") ) {
      final String tableName = tagName.substring(0, tagName.length() - "Type".length()) + "s";
      final Table table = register.getTable(tableName);
      if ( table != null && table.isPrimary() ) {
        return tableName;
      }
    }
    return "";
}

Add comments when:

• You need to explain intent in a way that is not obvious from your code.

  /* We're starting on the left side of the tree because production data indicates
   * about 80% of the time, queried nodes are in the left half. */
  
  /* In Civ V, a '%' is a wildcard, so detect if this string has a '%' character. */
  

• A part of your code is counter-intuitive or fragile, or to document code smells.

  array[index] = 5; // null-checked by array.length before
  
  if ( end = reachedEOF() ) // boolean assignment
  
  // don't call this recursively because it changes global context
  
  /* Copied from XYZ#refineMyCoffee */
  

• Naming or code assumes domain knowledge.

  /**
   * <p>Holds rows grouped by tags.
   * <p>A <dfn>Row</dfn> is a ...
   */
  public class Table {
  

In the end, it's as much a matter of personal style as it is a science or discipline. You are the developer and later maintainer of the project, so pick something you're comfortable with. When in doubt, err on the side of slightly over-documenting.