LocalSymbolTable.java
/*
* Copyright 2007-2019 Amazon.com, Inc. or its affiliates. All Rights Reserved.
*
* Licensed under the Apache License, Version 2.0 (the "License").
* You may not use this file except in compliance with the License.
* A copy of the License is located at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* or in the "license" file accompanying this file. This file is distributed
* on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
* express or implied. See the License for the specific language governing
* permissions and limitations under the License.
*/
package com.amazon.ion.impl;
import static com.amazon.ion.SystemSymbols.IMPORTS;
import static com.amazon.ion.SystemSymbols.IMPORTS_SID;
import static com.amazon.ion.SystemSymbols.ION;
import static com.amazon.ion.SystemSymbols.ION_SYMBOL_TABLE;
import static com.amazon.ion.SystemSymbols.MAX_ID_SID;
import static com.amazon.ion.SystemSymbols.NAME_SID;
import static com.amazon.ion.SystemSymbols.SYMBOLS_SID;
import static com.amazon.ion.SystemSymbols.VERSION_SID;
import static com.amazon.ion.impl._Private_Utils.copyOf;
import static com.amazon.ion.impl._Private_Utils.getSidForSymbolTableField;
import static com.amazon.ion.impl._Private_Utils.safeEquals;
import com.amazon.ion.IonCatalog;
import com.amazon.ion.IonException;
import com.amazon.ion.IonReader;
import com.amazon.ion.IonType;
import com.amazon.ion.IonWriter;
import com.amazon.ion.ReadOnlyValueException;
import com.amazon.ion.SymbolTable;
import com.amazon.ion.SymbolToken;
import com.amazon.ion.util.IonTextUtils;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
/**
* A local symbol table.
* <p>
* Instances of this class are safe for use by multiple threads.
*/
class LocalSymbolTable
implements _Private_LocalSymbolTable
{
static class Factory implements _Private_LocalSymbolTableFactory
{
private Factory(){} // Should be accessed through the singleton
public SymbolTable newLocalSymtab(IonCatalog catalog,
IonReader reader,
boolean alreadyInStruct)
{
List<String> symbolsList = new ArrayList<String>();
SymbolTable currentSymbolTable = reader.getSymbolTable();
LocalSymbolTableImports imports = readLocalSymbolTable(reader,
catalog,
alreadyInStruct,
symbolsList,
currentSymbolTable);
if (imports == null) {
// This was an LST append, so the existing symbol table was updated.
return currentSymbolTable;
}
return new LocalSymbolTable(imports, symbolsList);
}
public SymbolTable newLocalSymtab(SymbolTable defaultSystemSymtab,
SymbolTable... imports)
{
LocalSymbolTableImports unifiedSymtabImports =
new LocalSymbolTableImports(defaultSystemSymtab, imports);
return new LocalSymbolTable(unifiedSymtabImports,
null /* local symbols */);
}
}
static final Factory DEFAULT_LST_FACTORY = new Factory();
/**
* The initial length of {@link #mySymbolNames}.
*/
private static final int DEFAULT_CAPACITY = 16;
/**
* The system and shared symtabs imported by this symtab. Never null.
* <p>
* Note: this member field is immutable and assigned only during
* construction, hence no synchronization is needed for its method calls.
*/
private final LocalSymbolTableImports myImportsList;
/**
* Map of symbol names to symbol ids of local symbols that are not in
* imports.
*/
private final Map<String, Integer> mySymbolsMap;
/**
* Whether this symbol table is read only, and thus, immutable.
*/
private boolean isReadOnly;
/**
* The local symbol names declared in this symtab; never null.
* The sid of the first element is {@link #myFirstLocalSid}.
* Only the first {@link #mySymbolsCount} elements are valid.
*/
String[] mySymbolNames;
/**
* This is the number of symbols defined in this symbol table
* locally, that is not imported from some other table.
*/
int mySymbolsCount;
/**
* The sid of the first local symbol, which is stored at
* {@link #mySymbolNames}[0].
*/
final int myFirstLocalSid;
//==========================================================================
// Private constructor(s) and static factory methods
//==========================================================================
private void buildSymbolsMap()
{
int sid = myFirstLocalSid;
for (int i = 0; i < mySymbolNames.length; i++, sid++)
{
String symbolText = mySymbolNames[i];
if (symbolText != null)
{
putToMapIfNotThere(mySymbolsMap, symbolText, sid);
}
}
}
/**
* @param imports never null
* @param symbolsList may be null or empty
*/
protected LocalSymbolTable(LocalSymbolTableImports imports, List<String> symbolsList)
{
if (symbolsList == null || symbolsList.isEmpty())
{
mySymbolsCount = 0;
mySymbolNames = _Private_Utils.EMPTY_STRING_ARRAY;
}
else
{
mySymbolsCount = symbolsList.size();
mySymbolNames = symbolsList.toArray(new String[mySymbolsCount]);
}
myImportsList = imports;
myFirstLocalSid = myImportsList.getMaxId() + 1;
// Copy locally declared symbols to mySymbolsMap
// The initial size is chosen so that resizing is avoided. The default load factor is 0.75. Resizing
// could also be avoided by setting the initial size to mySymbolsCount and setting the load factor to
// 1.0, but this would lead to more hash collisions.
mySymbolsMap = new HashMap<String, Integer>((int) Math.ceil(mySymbolsCount / 0.75));
buildSymbolsMap();
}
/**
* Copy-constructor, performs defensive copying of member fields where
* necessary. The returned instance is mutable.
*/
protected LocalSymbolTable(LocalSymbolTable other, int maxId)
{
isReadOnly = false;
myFirstLocalSid = other.myFirstLocalSid;
myImportsList = other.myImportsList;
mySymbolsCount = maxId - myImportsList.getMaxId();
mySymbolNames = copyOf(other.mySymbolNames, mySymbolsCount);
// Copy locally declared symbols to mySymbolsMap
if (maxId == other.getMaxId())
{
// Shallow copy
mySymbolsMap = new HashMap<String, Integer>(other.mySymbolsMap);
}
else
{
mySymbolsMap = new HashMap<String, Integer>(mySymbolsCount);
buildSymbolsMap();
}
}
/**
* Parses the symbol table at the reader's current position.
* @param reader the reader from which to parse the symbol table.
* @param catalog the catalog from which to resolve shared symbol table imports.
* @param isOnStruct true if the reader is already positioned on the symbol table struct; otherwise, false.
* @param symbolsListOut list into which local symbols declared by the parsed symbol table will be deposited.
* @param currentSymbolTable the symbol table currently active in the stream.
* @return a new LocalSymbolTableImports instance, or null if this was an LST append. If null, `currentSymbolTable`
* continues to be the active symbol table.
*/
protected static LocalSymbolTableImports readLocalSymbolTable(IonReader reader,
IonCatalog catalog,
boolean isOnStruct,
List<String> symbolsListOut,
SymbolTable currentSymbolTable)
{
if (! isOnStruct)
{
reader.next();
}
assert reader.getType() == IonType.STRUCT
: "invalid symbol table image passed in reader " +
reader.getType() + " encountered when a struct was expected";
assert ION_SYMBOL_TABLE.equals(reader.getTypeAnnotations()[0])
: "local symbol tables must be annotated by " + ION_SYMBOL_TABLE;
reader.stepIn();
List<SymbolTable> importsList = new ArrayList<SymbolTable>();
importsList.add(reader.getSymbolTable().getSystemSymbolTable());
IonType fieldType;
boolean foundImportList = false;
boolean foundLocalSymbolList = false;
boolean isAppend = false;
while ((fieldType = reader.next()) != null)
{
if (reader.isNullValue()) continue;
SymbolToken symTok = reader.getFieldNameSymbol();
int sid = symTok.getSid();
if (sid == SymbolTable.UNKNOWN_SYMBOL_ID)
{
// This is a user-defined IonReader or a pure DOM, fall
// back to text
final String fieldName = reader.getFieldName();
sid = getSidForSymbolTableField(fieldName);
}
// TODO amazon-ion/ion-java/issues/36 Switching over SIDs doesn't cover the case
// where the relevant field names are defined by a prev LST;
// the prev LST could have 'symbols' defined locally with a
// different SID!
switch (sid)
{
case SYMBOLS_SID:
{
// As per the Spec, other field types are treated as
// empty lists
if(foundLocalSymbolList){
throw new IonException("Multiple symbol fields found within a single local symbol table.");
}
foundLocalSymbolList = true;
if (fieldType == IonType.LIST)
{
reader.stepIn();
IonType type;
while ((type = reader.next()) != null)
{
final String text;
if (type == IonType.STRING)
{
text = reader.stringValue();
}
else
{
text = null;
}
symbolsListOut.add(text);
}
reader.stepOut();
}
break;
}
case IMPORTS_SID:
{
if(foundImportList){
throw new IonException("Multiple imports fields found within a single local symbol table.");
}
foundImportList = true;
if (fieldType == IonType.LIST)
{
prepImportsList(importsList, reader, catalog);
}
else if (fieldType == IonType.SYMBOL && ION_SYMBOL_TABLE.equals(reader.stringValue()))
{
isAppend = true;
}
break;
}
default:
{
// As per the Spec, any other field is ignored
break;
}
}
}
reader.stepOut();
if (isAppend && currentSymbolTable.isLocalTable()) {
// Because the current symbol table is a local symbol table (i.e. not the system symbol table), it can
// be appended in-place.
LocalSymbolTable currentLocalSymbolTable = (LocalSymbolTable) currentSymbolTable;
for (String newSymbol : symbolsListOut) {
currentLocalSymbolTable.putSymbol(newSymbol);
}
return null;
}
return new LocalSymbolTableImports(importsList);
}
@Override
public synchronized _Private_LocalSymbolTable makeCopy()
{
return new LocalSymbolTable(this, getMaxId());
}
synchronized LocalSymbolTable makeCopy(int maxId)
{
return new LocalSymbolTable(this, maxId);
}
public boolean isLocalTable()
{
return true;
}
public boolean isSharedTable()
{
return false;
}
public boolean isSystemTable()
{
return false;
}
public boolean isSubstitute()
{
return false;
}
public synchronized boolean isReadOnly()
{
return isReadOnly;
}
public synchronized void makeReadOnly()
{
isReadOnly = true;
}
public int getImportedMaxId()
{
return myImportsList.getMaxId();
}
public synchronized int getMaxId()
{
int maxid = mySymbolsCount + myImportsList.getMaxId();
return maxid;
}
public int getVersion()
{
return 0;
}
public String getName()
{
return null;
}
public String getIonVersionId()
{
SymbolTable system_table = myImportsList.getSystemSymbolTable();
return system_table.getIonVersionId();
}
public synchronized Iterator<String> iterateDeclaredSymbolNames()
{
return new SymbolIterator(mySymbolNames, mySymbolsCount);
}
public String findKnownSymbol(int id)
{
String name = null;
if (id < 0)
{
String message = "symbol IDs must be >= 0";
throw new IllegalArgumentException(message);
}
else if (id < myFirstLocalSid)
{
name = myImportsList.findKnownSymbol(id);
}
else
{
int offset = id - myFirstLocalSid;
String[] names;
synchronized (this)
{
names = mySymbolNames;
}
if (offset < names.length)
{
name = names[offset];
}
}
return name;
}
public int findSymbol(String name)
{
// Look in system then imports
int sid = myImportsList.findSymbol(name);
// Look in local symbols
if (sid == UNKNOWN_SYMBOL_ID)
{
sid = findLocalSymbol(name);
}
return sid;
}
private int findLocalSymbol(String name)
{
Integer isid;
synchronized (this)
{
isid = mySymbolsMap.get(name);
}
if (isid != null)
{
assert isid != UNKNOWN_SYMBOL_ID;
return isid;
}
return UNKNOWN_SYMBOL_ID;
}
public synchronized SymbolToken intern(String text)
{
SymbolToken is = find(text);
if (is == null)
{
validateSymbol(text);
int sid = putSymbol(text);
is = new SymbolTokenImpl(text, sid);
}
return is;
}
public SymbolToken find(String text)
{
text.getClass(); // fast null check
// Look in system then imports
SymbolToken symTok = myImportsList.find(text);
// Look in local symbols
if (symTok == null)
{
Integer sid;
String[] names;
synchronized (this)
{
sid = mySymbolsMap.get(text);
names = mySymbolNames;
}
if (sid != null)
{
int offset = sid - myFirstLocalSid;
String internedText = names[offset];
assert internedText != null;
symTok = new SymbolTokenImpl(internedText, sid);
}
}
return symTok;
}
private static final void validateSymbol(String name)
{
if (name == null)
{
throw new IllegalArgumentException("symbols must not be null");
}
for (int i = 0; i < name.length(); ++i)
{
int c = name.charAt(i);
if (c >= 0xD800 && c <= 0xDFFF)
{
if (c >= 0xDC00)
{
String message = "unpaired trailing surrogate in symbol " +
"name at position " + i;
throw new IllegalArgumentException(message);
}
++i;
if (i == name.length())
{
String message = "unmatched leading surrogate in symbol " +
"name at position " + i;
throw new IllegalArgumentException(message);
}
c = name.charAt(i);
if (c < 0xDC00 || c > 0xDFFF)
{
String message = "unmatched leading surrogate in symbol " +
"name at position " + i;
throw new IllegalArgumentException(message);
}
}
}
}
/**
* NOT SYNCHRONIZED! Call within constructor or from synch'd method.
*/
int putSymbol(String symbolName)
{
if (isReadOnly)
{
throw new ReadOnlyValueException(SymbolTable.class);
}
if (mySymbolsCount == mySymbolNames.length)
{
int newlen = mySymbolsCount * 2;
if (newlen < DEFAULT_CAPACITY)
{
newlen = DEFAULT_CAPACITY;
}
String[] temp = new String[newlen];
System.arraycopy(mySymbolNames, 0, temp, 0, mySymbolsCount);
mySymbolNames = temp;
}
int sid = -1;
if (symbolName != null)
{
sid = mySymbolsCount + myFirstLocalSid;
assert sid == getMaxId() + 1;
putToMapIfNotThere(mySymbolsMap, symbolName, sid);
}
mySymbolNames[mySymbolsCount] = symbolName;
mySymbolsCount++;
return sid;
}
private static void putToMapIfNotThere(Map<String, Integer> symbolsMap,
String text,
int sid)
{
// When there's a duplicate name, don't replace the lower sid.
// This pattern avoids double-lookup in the normal happy case
// and only requires a second lookup when there's a duplicate.
Integer extantSid = symbolsMap.put(text, sid);
if (extantSid != null)
{
// We always insert symbols with increasing sids
assert extantSid < sid;
symbolsMap.put(text, extantSid);
}
}
public SymbolTable getSystemSymbolTable()
{
return myImportsList.getSystemSymbolTable();
}
public SymbolTable[] getImportedTables()
{
return myImportsList.getImportedTables();
}
@Override
public SymbolTable[] getImportedTablesNoCopy()
{
return myImportsList.getImportedTablesNoCopy();
}
@Override
public List<SymbolTable> getImportedTablesAsList() {
throw new UnsupportedOperationException("Call getImportedTablesNoCopy() instead.");
}
@Override
public Collection<String> getLocalSymbolsNoCopy() {
throw new UnsupportedOperationException("If this is needed, add a no-copy variant that returns an array.");
}
@Override
public int getNumberOfLocalSymbols() {
return mySymbolsCount;
}
public void writeTo(IonWriter writer) throws IOException
{
IonReader reader = new SymbolTableReader(this);
writer.writeValues(reader);
}
/**
* Collects the necessary imports from the reader and catalog, and load
* them into the passed-in {@code importsList}.
*/
private static void prepImportsList(List<SymbolTable> importsList,
IonReader reader,
IonCatalog catalog)
{
assert IMPORTS.equals(reader.getFieldName());
reader.stepIn();
IonType t;
while ((t = reader.next()) != null)
{
if (!reader.isNullValue() && t == IonType.STRUCT)
{
SymbolTable importedTable = readOneImport(reader, catalog);
if (importedTable != null)
{
importsList.add(importedTable);
}
}
}
reader.stepOut();
}
/**
* Returns a {@link SymbolTable} representation of a single import
* declaration from the passed-in reader and catalog.
*
* @return
* symbol table representation of the import; null if the import
* declaration is malformed
*/
private static SymbolTable readOneImport(IonReader ionRep,
IonCatalog catalog)
{
assert (ionRep.getType() == IonType.STRUCT);
String name = null;
int version = -1;
int maxid = -1;
ionRep.stepIn();
IonType t;
while ((t = ionRep.next()) != null)
{
if (ionRep.isNullValue()) continue;
SymbolToken symTok = ionRep.getFieldNameSymbol();
int field_id = symTok.getSid();
if (field_id == UNKNOWN_SYMBOL_ID)
{
// this is a user defined reader or a pure DOM
// we fall back to text here
final String fieldName = ionRep.getFieldName();
field_id = getSidForSymbolTableField(fieldName);
}
switch(field_id)
{
case NAME_SID:
if (t == IonType.STRING)
{
name = ionRep.stringValue();
}
break;
case VERSION_SID:
if (t == IonType.INT)
{
version = ionRep.intValue();
}
break;
case MAX_ID_SID:
if (t == IonType.INT)
{
maxid = ionRep.intValue();
}
break;
default:
// we just ignore anything else as "open content"
break;
}
}
ionRep.stepOut();
// Ignore import clauses with malformed name field.
if (name == null || name.length() == 0 || name.equals(ION))
{
return null;
}
if (version < 1)
{
version = 1;
}
SymbolTable itab = null;
if (catalog != null)
{
itab = catalog.getTable(name, version);
}
if (maxid < 0)
{
if (itab == null || version != itab.getVersion())
{
String message =
"Import of shared table "
+ IonTextUtils.printString(name)
+ " lacks a valid max_id field, but an exact match was not"
+ " found in the catalog";
if (itab != null)
{
message += " (found version " + itab.getVersion() + ")";
}
// TODO custom exception
throw new IonException(message);
}
// Exact match is found, but max_id is undefined in import
// declaration, set max_id to largest sid of shared symtab
maxid = itab.getMaxId();
}
if (itab == null)
{
assert maxid >= 0;
// Construct substitute table with max_id undefined symbols
itab = new SubstituteSymbolTable(name, version, maxid);
}
else if (itab.getVersion() != version || itab.getMaxId() != maxid)
{
// A match was found BUT specs are not an exact match
// Construct a substitute with correct specs, containing the
// original import table that was found
itab = new SubstituteSymbolTable(itab, version, maxid);
}
return itab;
}
/**
* Generate the string representation of a symbol with an unknown id.
* @param id must be a value greater than zero.
* @return the symbol name, of the form <code>$NNN</code> where NNN is the
* integer rendering of <code>id</code>
*/
public static String unknownSymbolName(int id)
{
assert id > 0;
return "$" + id;
}
@Override
public String toString()
{
return "(LocalSymbolTable max_id:" + getMaxId() + ')';
}
private static final class SymbolIterator
implements Iterator<String>
{
private final String[] mySymbolNames;
private final int mySymbolsCount;
private int _idx = 0;
SymbolIterator(String[] symbolNames, int count)
{
mySymbolNames = symbolNames;
mySymbolsCount = count;
}
public boolean hasNext()
{
if (_idx < mySymbolsCount)
{
return true;
}
return false;
}
public String next()
{
if (_idx < mySymbolsCount)
{
return mySymbolNames[_idx++];
}
throw new NoSuchElementException();
}
public void remove()
{
throw new UnsupportedOperationException();
}
}
/**
* This method, and the context from which it is called, assumes that the
* symtabs are not being mutated by another thread.
* Therefore it doesn't use synchronization.
*/
boolean symtabExtends(SymbolTable other)
{
// Throws ClassCastException if other isn't a local symtab
LocalSymbolTable subset = (LocalSymbolTable) other;
// Gather snapshots of each LST's data, so we don't
// Superset must have same/more known symbols than subset.
if (getMaxId() < subset.getMaxId()) return false;
// TODO amazon-ion/ion-java/issues/18 Currently, we check imports by their refs. which
// might be overly strict; imports which are not the same ref.
// but have the same semantic states fails the extension check.
if (! myImportsList.equalImports(subset.myImportsList))
return false;
int subLocalSymbolCount = subset.mySymbolsCount;
// Superset extends subset if subset doesn't have any declared symbols.
if (subLocalSymbolCount == 0) return true;
// Superset must have same/more declared (local) symbols than subset.
if (mySymbolsCount < subLocalSymbolCount) return false;
String[] subsetSymbols = subset.mySymbolNames;
// Before we go through the expensive iteration from the front,
// check the last (largest) declared symbol in subset beforehand
if (! safeEquals(mySymbolNames[subLocalSymbolCount- 1],
subsetSymbols[subLocalSymbolCount- 1]))
{
return false;
}
// Now, we iterate from the first declared symbol, note that the
// iteration below is O(n)!
for (int i = 0; i < subLocalSymbolCount - 1; i++)
{
if (! safeEquals(mySymbolNames[i], subsetSymbols[i]))
return false;
}
return true;
}
}