unicode/c/genprops/pnamesbuilder.cpp - external/github.com/unicode-org/icu - Git at Google

 /*
 **********************************************************************
 *   Copyright (C) 2002-2012, International Business Machines
 *   Corporation and others.  All Rights Reserved.
 **********************************************************************
 *   Date        Name        Description
 *   10/11/02    aliu        Creation.
 *   2010nov19   Markus Scherer  Rewrite for formatVersion 2.
 *   2011dec18   Markus Scherer  Moved genpname/genpname.cpp to genprops/pnamesbuilder.cpp.
 **********************************************************************
 */

 #include "unicode/utypes.h"
 #include "unicode/bytestrie.h"
 #include "unicode/bytestriebuilder.h"
 #include "unicode/putil.h"
 #include "unicode/uclean.h"
 #include "charstr.h"
 #include "cstring.h"
 #include "denseranges.h"
 #include "genprops.h"
 #include "propname.h"
 #include "toolutil.h"
 #include "uhash.h"
 #include "uinvchar.h"
 #include "unewdata.h"
 #include "uvectr32.h"
 #include "writesrc.h"

 #include <stdio.h>

 // We test for ASCII delimiters and White_Space, and build ASCII string BytesTries.
 #if U_CHARSET_FAMILY!=U_ASCII_FAMILY
 #   error This builder requires U_CHARSET_FAMILY==U_ASCII_FAMILY.
 #endif

 U_NAMESPACE_USE

 //----------------------------------------------------------------------
 // BEGIN DATA
 //
 // This is the raw data to be output.  We define the data structure,
 // then include a machine-generated header that contains the actual
 // data.

 #include "unicode/uchar.h"
 #include "unicode/unorm2.h"
 #include "unicode/uscript.h"

 // Dilemma: We want to use MAX_ALIASES to define fields in the Value class.
 // However, we need to define the class before including the data header
 // and we can use MAX_ALIASES only after including it.
 // So we define a second constant and at runtime check that it's >=MAX_ALIASES.
 static const int32_t VALUE_MAX_ALIASES=4;

 static const int32_t JOINED_ALIASES_CAPACITY=100;

 class Value {
 public:
     Value(int32_t enumValue, const char *joinedAliases)
             : enumValue(enumValue), joinedAliases(joinedAliases), count(0) {
         if(uprv_strlen(joinedAliases)>=JOINED_ALIASES_CAPACITY) {
             fprintf(stderr,
                     "genprops error: pnamesbuilder.cpp Value::Value(%ld, \"%s\"): "
                     "joined aliases too long: "
                     "increase JOINED_ALIASES_CAPACITY, to at least %ld\n",
                     (long)enumValue, joinedAliases, uprv_strlen(joinedAliases)+1);
             exit(U_BUFFER_OVERFLOW_ERROR);
         }
         // Copy the space-separated aliases into NUL-separated ones and count them.
         // Write a normalized version of each one.
         const char *j=joinedAliases;
         char *a=aliasesBuffer;
         char *n=normalizedBuffer;
         char c;
         do {
             aliases[count]=a;
             normalized[count++]=n;
             while((c=*j++)!=' ' && c!=0) {
                 *a++=c;
                 // Ignore delimiters '-' and '_'.
                 if(!(c=='-' || c=='_')) {
                     *n++=uprv_tolower(c);
                 }
             }
             *a++=0;
             *n++=0;
         } while(c!=0);
     }

     /**
      * Writes at most MAX_ALIASES pointers for unique normalized aliases
      * (no empty strings) to dest and returns how many there are.
      */
     int32_t getUniqueNormalizedAliases(const char *dest[]) const {
         int32_t numUnique=0;
         for(int32_t i=0; i<count; ++i) {
             const char *s=normalized[i];
             if(*s!=0) {  // Omit empty strings.
                 for(int32_t j=0;; ++j) {
                     if(j==numUnique) {
                         // s is a new unique alias.
                         dest[numUnique++]=s;
                         break;
                     }
                     if(0==uprv_strcmp(s, dest[j])) {
                         // s is equal or equivalent to an earlier alias.
                         break;
                     }
                 }
             }
         }
         return numUnique;
     }

     int32_t enumValue;
     const char *joinedAliases;
     char aliasesBuffer[JOINED_ALIASES_CAPACITY];
     char normalizedBuffer[JOINED_ALIASES_CAPACITY];
     const char *aliases[VALUE_MAX_ALIASES];
     const char *normalized[VALUE_MAX_ALIASES];
     int32_t count;
 };

 class Property : public Value {
 public:
     // A property with a values array.
     Property(int32_t enumValue, const char *joinedAliases,
              const Value *values, int32_t valueCount)
             : Value(enumValue, joinedAliases),
               values(values), valueCount(valueCount) {}
     // A binary property (enumValue<UCHAR_BINARY_LIMIT), or one without values.
     Property(int32_t enumValue, const char *joinedAliases);

     const Value *values;
     int32_t valueCount;
 };

 // *** Include the data header ***
 #include "pnames_data.h"

 Property::Property(int32_t enumValue, const char *joinedAliases)
         : Value(enumValue, joinedAliases),
           values(enumValue<UCHAR_BINARY_LIMIT ? VALUES_binprop : NULL),
           valueCount(enumValue<UCHAR_BINARY_LIMIT ? 2 : 0) {}

 // END DATA
 //----------------------------------------------------------------------

 class PNamesPropertyNames : public PropertyNames {
 public:
     PNamesPropertyNames()
             : valueMaps(NULL), bytesTries(NULL) {}
     void init(const int32_t *vm, const uint8_t *bt) {
         valueMaps=vm;
         bytesTries=bt;
     }
     virtual int32_t getPropertyEnum(const char *name) const;
     virtual int32_t getPropertyValueEnum(int32_t property, const char *name) const;
 private:
     int32_t findProperty(int32_t property) const;
     UBool containsName(BytesTrie &trie, const char *name) const;
     int32_t getPropertyOrValueEnum(int32_t bytesTrieOffset, const char *alias) const;

     const int32_t *valueMaps;
     const uint8_t *bytesTries;
 };

 class PNamesBuilderImpl : public PNamesBuilder {
 public:
     PNamesBuilderImpl(UErrorCode &errorCode)
             : valueMaps(errorCode), btb(errorCode), maxNameLength(0),
               nameGroupToOffset(NULL) {}

     ~PNamesBuilderImpl() {
         uhash_close(nameGroupToOffset);
     }

     virtual void build(UErrorCode &errorCode) {
         if(U_FAILURE(errorCode)) { return; }
         if(VALUE_MAX_ALIASES<MAX_ALIASES) {
             fprintf(stderr,
                     "genprops error: pnamesbuilder.cpp VALUE_MAX_ALIASES=%d<%d=MAX_ALIASES -- "
                     "need to change VALUE_MAX_ALIASES to at least %d\n",
                     (int)VALUE_MAX_ALIASES, (int)MAX_ALIASES, (int)MAX_ALIASES);
             errorCode=U_INTERNAL_PROGRAM_ERROR;
             return;
         }
         nameGroupToOffset=uhash_open(uhash_hashChars, uhash_compareChars, NULL, &errorCode);
         // Build main property aliases value map at value map offset 0,
         // so that we need not store another offset for it.
         UVector32 propEnums(errorCode);
         int32_t propIndex;
         for(propIndex=0; propIndex<LENGTHOF(PROPERTIES); ++propIndex) {
             propEnums.sortedInsert(PROPERTIES[propIndex].enumValue, errorCode);
         }
         int32_t ranges[10][2];
         int32_t numPropRanges=uprv_makeDenseRanges(propEnums.getBuffer(),
                                                    LENGTHOF(PROPERTIES), 0x100,
                                                    ranges, LENGTHOF(ranges));
         valueMaps.addElement(numPropRanges, errorCode);
         int32_t i, j;
         for(i=0; i<numPropRanges; ++i) {
             valueMaps.addElement(ranges[i][0], errorCode);
             valueMaps.addElement(ranges[i][1]+1, errorCode);
             for(j=ranges[i][0]; j<=ranges[i][1]; ++j) {
                 // Reserve two slots per property for the name group offset and the value-map offset.
                 valueMaps.addElement(0, errorCode);
                 valueMaps.addElement(0, errorCode);
             }
         }

         // Build the properties trie first, at BytesTrie offset 0,
         // so that we need not store another offset for it.
         buildPropertiesBytesTrie(PROPERTIES, LENGTHOF(PROPERTIES), errorCode);

         // Build the name group for the first property, at nameGroups offset 0.
         // Name groups for *value* aliases must not start at offset 0
         // because that is a missing-value marker for sparse value ranges.
         setPropertyInt(PROPERTIES[0].enumValue, 0,
                        writeValueAliases(PROPERTIES[0], errorCode));

         // Build the known-repeated binary properties once.
         int32_t binPropsValueMapOffset=valueMaps.size();
         int32_t bytesTrieOffset=buildValuesBytesTrie(VALUES_binprop, 2, errorCode);
         valueMaps.addElement(bytesTrieOffset, errorCode);
         buildValueMap(VALUES_binprop, 2, errorCode);

         // Note: It is slightly wasteful to store binary properties like all others.
         // Since we know that they are in the lowest range of property enum values
         // and share the same name group and BytesTrie,
         // we could just store those two indexes once.
         // (This would save 8 bytes per binary property, or about half a kilobyte.)

         // Build the known-repeated canonical combining class properties once.
         int32_t cccValueMapOffset=valueMaps.size();
         bytesTrieOffset=buildValuesBytesTrie(VALUES_ccc, LENGTHOF(VALUES_ccc), errorCode);
         valueMaps.addElement(bytesTrieOffset, errorCode);
         buildValueMap(VALUES_ccc, LENGTHOF(VALUES_ccc), errorCode);

         // Build the rest of the data.
         for(propIndex=0; propIndex<LENGTHOF(PROPERTIES); ++propIndex) {
             if(propIndex>0) {
                 // writeValueAliases(PROPERTIES[0], ...) already done
                 setPropertyInt(PROPERTIES[propIndex].enumValue, 0,
                                writeValueAliases(PROPERTIES[propIndex], errorCode));
             }
             int32_t valueCount=PROPERTIES[propIndex].valueCount;
             if(valueCount>0) {
                 int32_t valueMapOffset;
                 const Value *values=PROPERTIES[propIndex].values;
                 if(values==VALUES_binprop) {
                     valueMapOffset=binPropsValueMapOffset;
                 } else if(values==VALUES_ccc || values==VALUES_lccc || values==VALUES_tccc) {
                     valueMapOffset=cccValueMapOffset;
                 } else {
                     valueMapOffset=valueMaps.size();
                     bytesTrieOffset=buildValuesBytesTrie(values, valueCount, errorCode);
                     valueMaps.addElement(bytesTrieOffset, errorCode);
                     buildValueMap(values, valueCount, errorCode);
                 }
                 setPropertyInt(PROPERTIES[propIndex].enumValue, 1, valueMapOffset);
             }
         }

         // Write the indexes.
         int32_t offset=(int32_t)sizeof(indexes);
         indexes[PropNameData::IX_VALUE_MAPS_OFFSET]=offset;
         offset+=valueMaps.size()*4;
         indexes[PropNameData::IX_BYTE_TRIES_OFFSET]=offset;
         offset+=bytesTries.length();
         indexes[PropNameData::IX_NAME_GROUPS_OFFSET]=offset;
         offset+=nameGroups.length();
         for(i=PropNameData::IX_RESERVED3_OFFSET; i<=PropNameData::IX_TOTAL_SIZE; ++i) {
             indexes[i]=offset;
         }
         indexes[PropNameData::IX_MAX_NAME_LENGTH]=maxNameLength;
         for(i=PropNameData::IX_RESERVED7; i<PropNameData::IX_COUNT; ++i) {
             indexes[i]=0;
         }

         if(!beQuiet) {
             puts("* pnames.icu stats *");
             printf("length of all value maps:  %6ld\n", (long)valueMaps.size());
             printf("length of all BytesTries:  %6ld\n", (long)bytesTries.length());
             printf("length of all name groups: %6ld\n", (long)nameGroups.length());
             printf("length of pnames.icu data: %6ld\n", (long)indexes[PropNameData::IX_TOTAL_SIZE]);
         }
     }

     virtual void writeCSourceFile(const char *path, UErrorCode &errorCode);
     virtual void writeBinaryData(const char *path, UBool withCopyright, UErrorCode &errorCode);

     int32_t writeValueAliases(const Value &value, UErrorCode &errorCode) {
         int32_t nameOffset=uhash_geti(nameGroupToOffset, (void *)value.joinedAliases);
         if(nameOffset!=0) {
             // The same list of aliases has been written already.
             return nameOffset-1;  // Was incremented to reserve 0 for "not found".
         }
         // Write this not-yet-seen list of aliases.
         nameOffset=nameGroups.length();
         uhash_puti(nameGroupToOffset, (void *)value.joinedAliases,
                    nameOffset+1, &errorCode);
         // The first byte tells us how many aliases there are.
         // We use only values 0..0x1f in the first byte because when we write
         // the name groups as an invariant-character string into a source file,
         // those values (C0 control codes) are written as numbers rather than as characters.
         int32_t count=value.count;
         if(count>=0x20) {
             fprintf(stderr, "Error: Too many aliases in \"%s\"\n", value.joinedAliases);
             exit(U_INDEX_OUTOFBOUNDS_ERROR);
         }
         nameGroups.append((char)count, errorCode);
         // There is at least a short name (sometimes empty) and a long name. (count>=2)
         // Note: Sometimes the short and long names are the same.
         // In such a case, we could set a flag and omit the duplicate,
         // but that would save only about 1.35% of total data size (Unicode 6.0/ICU 4.6)
         // which is not worth the trouble.
         // Note: In Unicode 6.1, there are more duplicates due to newly added
         // short names for blocks and other properties.
         // It might now be worth changing the data structure.
         for(int32_t i=0; i<count; ++i) {
             const char *s=value.aliases[i];
             int32_t sLength=uprv_strlen(s)+1;
             if(sLength>maxNameLength) {
                 maxNameLength=sLength;
             }
             nameGroups.append(s, sLength, errorCode);  // including NUL
         }
         return nameOffset;
     }

     void buildValueMap(const Value values[], int32_t length, UErrorCode &errorCode) {
         UVector32 sortedValues(errorCode);
         UVector32 nameOffsets(errorCode);  // Parallel to values[].
         int32_t i;
         for(i=0; i<length; ++i) {
             sortedValues.sortedInsert(values[i].enumValue, errorCode);
             nameOffsets.addElement(writeValueAliases(values[i], errorCode), errorCode);
         }
         int32_t ranges[10][2];
         int32_t numRanges=uprv_makeDenseRanges(sortedValues.getBuffer(), length, 0xe0,
                                                ranges, LENGTHOF(ranges));
         if(numRanges>0) {
             valueMaps.addElement(numRanges, errorCode);
             for(i=0; i<numRanges; ++i) {
                 valueMaps.addElement(ranges[i][0], errorCode);
                 valueMaps.addElement(ranges[i][1]+1, errorCode);
                 for(int32_t j=ranges[i][0]; j<=ranges[i][1]; ++j) {
                     // The range might not be completely dense, so j might not have an entry,
                     // in which case we write a nameOffset of 0.
                     // Real nameOffsets for property values are never 0.
                     // (The first name group is for the first property name.)
                     int32_t valueIndex=valuesIndexOf(values, length, j);
                     int32_t nameOffset= valueIndex>=0 ? nameOffsets.elementAti(valueIndex) : 0;
                     valueMaps.addElement(nameOffset, errorCode);
                 }
             }
         } else {
             // No dense ranges.
             valueMaps.addElement(0x10+length, errorCode);
             for(i=0; i<length; ++i) {
                 valueMaps.addElement(sortedValues.elementAti(i), errorCode);
             }
             for(i=0; i<length; ++i) {
                 valueMaps.addElement(
                     nameOffsets.elementAti(
                         valuesIndexOf(values, length,
                                        sortedValues.elementAti(i))), errorCode);
             }
         }
     }

     static int32_t valuesIndexOf(const Value values[], int32_t length, int32_t value) {
         for(int32_t i=0;; ++i) {
             if(values[i].enumValue==value) {
                 return i;
             }
         }
         return -1;
     }

     void setPropertyInt(int32_t prop, int32_t subIndex, int32_t value) {
         // Assume that prop is in the valueMaps.elementAti(0) ranges.
         int32_t index=1;
         for(;;) {
             int32_t rangeStart=valueMaps.elementAti(index);
             int32_t rangeLimit=valueMaps.elementAti(index+1);
             index+=2;
             if(rangeStart<=prop && prop<rangeLimit) {
                 valueMaps.setElementAt(value, index+2*(prop-rangeStart)+subIndex);
                 break;
             }
             index+=2*(rangeLimit-rangeStart);
         }
     }

     void addValueToBytesTrie(const Value &value, UErrorCode &errorCode) {
         const char *aliases[MAX_ALIASES];
         int32_t numAliases=value.getUniqueNormalizedAliases(aliases);
         for(int32_t i=0; i<numAliases; ++i) {
             btb.add(aliases[i], value.enumValue, errorCode);
         }
     }

     int32_t buildValuesBytesTrie(const Value values[], int32_t length, UErrorCode &errorCode) {
         btb.clear();
         for(int32_t i=0; i<length; ++i) {
             addValueToBytesTrie(values[i], errorCode);
         }
         int32_t bytesTrieOffset=bytesTries.length();
         bytesTries.append(btb.buildStringPiece(USTRINGTRIE_BUILD_SMALL, errorCode), errorCode);
         return bytesTrieOffset;
     }

     // Variant of buildValuesBytesTrie() for Property.
     // Property is-a Value, and the source code is the same,
     // but when we iterate through the array we need to increment by the right object size.
     int32_t buildPropertiesBytesTrie(const Property properties[], int32_t length,
                                      UErrorCode &errorCode) {
         btb.clear();
         for(int32_t i=0; i<length; ++i) {
             addValueToBytesTrie(properties[i], errorCode);
         }
         int32_t bytesTrieOffset=bytesTries.length();
         bytesTries.append(btb.buildStringPiece(USTRINGTRIE_BUILD_SMALL, errorCode), errorCode);
         return bytesTrieOffset;
     }

     virtual const PropertyNames *getPropertyNames() {
         pnames.init(valueMaps.getBuffer(),
                     reinterpret_cast<const uint8_t *>(bytesTries.data()));
         return &pnames;
     }

 private:
     int32_t indexes[PropNameData::IX_COUNT];
     UVector32 valueMaps;
     BytesTrieBuilder btb;
     CharString bytesTries;
     CharString nameGroups;
     int32_t maxNameLength;
     PNamesPropertyNames pnames;
     UHashtable *nameGroupToOffset;
 };

 /* UDataInfo cf. udata.h */
 static const UDataInfo dataInfo = {
     sizeof(UDataInfo),
     0,

     U_IS_BIG_ENDIAN,
     U_CHARSET_FAMILY,
     sizeof(UChar),
     0,

     { PNAME_SIG_0, PNAME_SIG_1, PNAME_SIG_2, PNAME_SIG_3 },
     { 2, 0, 0, 0 },                 /* formatVersion */
     UNICODE_VERSION
 };

 void
 PNamesBuilderImpl::writeBinaryData(const char *path, UBool withCopyright, UErrorCode &errorCode) {
     if(U_FAILURE(errorCode)) { return; }
     UNewDataMemory *pdata=udata_create(path, PNAME_DATA_TYPE, PNAME_DATA_NAME, &dataInfo,
                                        withCopyright ? U_COPYRIGHT_STRING : 0, &errorCode);
     if(U_FAILURE(errorCode)) {
         fprintf(stderr, "genprops: udata_create(%s, pnames.icu) failed - %s\n",
                 path, u_errorName(errorCode));
         return;
     }

     udata_writeBlock(pdata, indexes, PropNameData::IX_COUNT*4);
     udata_writeBlock(pdata, valueMaps.getBuffer(), valueMaps.size()*4);
     udata_writeBlock(pdata, bytesTries.data(), bytesTries.length());
     udata_writeBlock(pdata, nameGroups.data(), nameGroups.length());

     int32_t dataLength=(int32_t)udata_finish(pdata, &errorCode);
     if(dataLength!=indexes[PropNameData::IX_TOTAL_SIZE]) {
         fprintf(stderr,
                 "udata_finish(pnames.icu) reports %ld bytes written but should be %ld\n",
                 (long)dataLength, (long)indexes[PropNameData::IX_TOTAL_SIZE]);
         errorCode=U_INTERNAL_PROGRAM_ERROR;
     }
 }

 void
 PNamesBuilderImpl::writeCSourceFile(const char *path, UErrorCode &errorCode) {
     if(U_FAILURE(errorCode)) { return; }
     FILE *f=usrc_create(path, "propname_data.h",
                         "icu/tools/unicode/c/genprops/pnamesbuilder.cpp");
     if(f==NULL) {
         errorCode=U_FILE_ACCESS_ERROR;
         return;
     }

     fputs("#ifndef INCLUDED_FROM_PROPNAME_CPP\n"
           "#   error This file must be #included from propname.cpp only.\n"
           "#endif\n\n", f);

     fputs("U_NAMESPACE_BEGIN\n\n", f);

     usrc_writeArray(f, "const int32_t PropNameData::indexes[%ld]={",
                     indexes, 32, PropNameData::IX_COUNT,
                     "};\n\n");
     usrc_writeArray(f, "const int32_t PropNameData::valueMaps[%ld]={\n",
                     valueMaps.getBuffer(), 32, valueMaps.size(),
                     "\n};\n\n");
     usrc_writeArray(f, "const uint8_t PropNameData::bytesTries[%ld]={\n",
                     bytesTries.data(), 8, bytesTries.length(),
                     "\n};\n\n");
     usrc_writeArrayOfMostlyInvChars(
         f, "const char PropNameData::nameGroups[%ld]={\n",
         nameGroups.data(), nameGroups.length(),
         "\n};\n\n");

     fputs("U_NAMESPACE_END\n", f);

     fclose(f);
 }

 PNamesBuilder *
 createPNamesBuilder(UErrorCode &errorCode) {
     if(U_FAILURE(errorCode)) { return NULL; }
     PNamesBuilder *pb=new PNamesBuilderImpl(errorCode);
     if(pb==NULL) {
         errorCode=U_MEMORY_ALLOCATION_ERROR;
     }
     return pb;
 }

 // Note: The following is a partial copy of runtime propname.cpp code.
 // Consider changing that into a semi-public API to avoid duplication.

 int32_t PNamesPropertyNames::findProperty(int32_t property) const {
     int32_t i=1;  // valueMaps index, initially after numRanges
     for(int32_t numRanges=valueMaps[0]; numRanges>0; --numRanges) {
         // Read and skip the start and limit of this range.
         int32_t start=valueMaps[i];
         int32_t limit=valueMaps[i+1];
         i+=2;
         if(property<start) {
             break;
         }
         if(property<limit) {
             return i+(property-start)*2;
         }
         i+=(limit-start)*2;  // Skip all entries for this range.
     }
     return 0;
 }

 UBool PNamesPropertyNames::containsName(BytesTrie &trie, const char *name) const {
     if(name==NULL) {
         return FALSE;
     }
     UStringTrieResult result=USTRINGTRIE_NO_VALUE;
     char c;
     while((c=*name++)!=0) {
         c=uprv_invCharToLowercaseAscii(c);
         // Ignore delimiters '-', '_', and ASCII White_Space.
         if(c==0x2d || c==0x5f || c==0x20 || (0x09<=c && c<=0x0d)) {
             continue;
         }
         if(!USTRINGTRIE_HAS_NEXT(result)) {
             return FALSE;
         }
         result=trie.next((uint8_t)c);
     }
     return USTRINGTRIE_HAS_VALUE(result);
 }

 int32_t PNamesPropertyNames::getPropertyOrValueEnum(int32_t bytesTrieOffset, const char *alias) const {
     BytesTrie trie(bytesTries+bytesTrieOffset);
     if(containsName(trie, alias)) {
         return trie.getValue();
     } else {
         return UCHAR_INVALID_CODE;
     }
 }

 int32_t
 PNamesPropertyNames::getPropertyEnum(const char *alias) const {
     return getPropertyOrValueEnum(0, alias);
 }

 int32_t
 PNamesPropertyNames::getPropertyValueEnum(int32_t property, const char *alias) const {
     int32_t valueMapIndex=findProperty(property);
     if(valueMapIndex==0) {
         return UCHAR_INVALID_CODE;  // Not a known property.
     }
     valueMapIndex=valueMaps[valueMapIndex+1];
     if(valueMapIndex==0) {
         return UCHAR_INVALID_CODE;  // The property does not have named values.
     }
     // valueMapIndex is the start of the property's valueMap,
     // where the first word is the BytesTrie offset.
     return getPropertyOrValueEnum(valueMaps[valueMapIndex], alias);
 }
	/*
	**********************************************************************
	* Copyright (C) 2002-2012, International Business Machines
	* Corporation and others. All Rights Reserved.
	**********************************************************************
	* Date Name Description
	* 10/11/02 aliu Creation.
	* 2010nov19 Markus Scherer Rewrite for formatVersion 2.
	* 2011dec18 Markus Scherer Moved genpname/genpname.cpp to genprops/pnamesbuilder.cpp.
	**********************************************************************
	*/

	#include "unicode/utypes.h"
	#include "unicode/bytestrie.h"
	#include "unicode/bytestriebuilder.h"
	#include "unicode/putil.h"
	#include "unicode/uclean.h"
	#include "charstr.h"
	#include "cstring.h"
	#include "denseranges.h"
	#include "genprops.h"
	#include "propname.h"
	#include "toolutil.h"
	#include "uhash.h"
	#include "uinvchar.h"
	#include "unewdata.h"
	#include "uvectr32.h"
	#include "writesrc.h"

	#include <stdio.h>

	// We test for ASCII delimiters and White_Space, and build ASCII string BytesTries.
	#if U_CHARSET_FAMILY!=U_ASCII_FAMILY
	# error This builder requires U_CHARSET_FAMILY==U_ASCII_FAMILY.
	#endif

	U_NAMESPACE_USE

	//----------------------------------------------------------------------
	// BEGIN DATA
	//
	// This is the raw data to be output. We define the data structure,
	// then include a machine-generated header that contains the actual
	// data.

	#include "unicode/uchar.h"
	#include "unicode/unorm2.h"
	#include "unicode/uscript.h"

	// Dilemma: We want to use MAX_ALIASES to define fields in the Value class.
	// However, we need to define the class before including the data header
	// and we can use MAX_ALIASES only after including it.
	// So we define a second constant and at runtime check that it's >=MAX_ALIASES.
	static const int32_t VALUE_MAX_ALIASES=4;

	static const int32_t JOINED_ALIASES_CAPACITY=100;

	class Value {
	public:
	Value(int32_t enumValue, const char *joinedAliases)
	: enumValue(enumValue), joinedAliases(joinedAliases), count(0) {
	if(uprv_strlen(joinedAliases)>=JOINED_ALIASES_CAPACITY) {
	fprintf(stderr,
	"genprops error: pnamesbuilder.cpp Value::Value(%ld, \"%s\"): "
	"joined aliases too long: "
	"increase JOINED_ALIASES_CAPACITY, to at least %ld\n",
	(long)enumValue, joinedAliases, uprv_strlen(joinedAliases)+1);
	exit(U_BUFFER_OVERFLOW_ERROR);
	}
	// Copy the space-separated aliases into NUL-separated ones and count them.
	// Write a normalized version of each one.
	const char *j=joinedAliases;
	char *a=aliasesBuffer;
	char *n=normalizedBuffer;
	char c;
	do {
	aliases[count]=a;
	normalized[count++]=n;
	while((c=*j++)!=' ' && c!=0) {
	*a++=c;
	// Ignore delimiters '-' and '_'.
	if(!(c=='-' \|\| c=='_')) {
	*n++=uprv_tolower(c);
	}
	}
	*a++=0;
	*n++=0;
	} while(c!=0);
	}

	/**
	* Writes at most MAX_ALIASES pointers for unique normalized aliases
	* (no empty strings) to dest and returns how many there are.
	*/
	int32_t getUniqueNormalizedAliases(const char *dest[]) const {
	int32_t numUnique=0;
	for(int32_t i=0; i<count; ++i) {
	const char *s=normalized[i];
	if(*s!=0) { // Omit empty strings.
	for(int32_t j=0;; ++j) {
	if(j==numUnique) {
	// s is a new unique alias.
	dest[numUnique++]=s;
	break;
	}
	if(0==uprv_strcmp(s, dest[j])) {
	// s is equal or equivalent to an earlier alias.
	break;
	}
	}
	}
	}
	return numUnique;
	}

	int32_t enumValue;
	const char *joinedAliases;
	char aliasesBuffer[JOINED_ALIASES_CAPACITY];
	char normalizedBuffer[JOINED_ALIASES_CAPACITY];
	const char *aliases[VALUE_MAX_ALIASES];
	const char *normalized[VALUE_MAX_ALIASES];
	int32_t count;
	};

	class Property : public Value {
	public:
	// A property with a values array.
	Property(int32_t enumValue, const char *joinedAliases,
	const Value *values, int32_t valueCount)
	: Value(enumValue, joinedAliases),
	values(values), valueCount(valueCount) {}
	// A binary property (enumValue<UCHAR_BINARY_LIMIT), or one without values.
	Property(int32_t enumValue, const char *joinedAliases);

	const Value *values;
	int32_t valueCount;
	};

	// * Include the data header *
	#include "pnames_data.h"

	Property::Property(int32_t enumValue, const char *joinedAliases)
	: Value(enumValue, joinedAliases),
	values(enumValue<UCHAR_BINARY_LIMIT ? VALUES_binprop : NULL),
	valueCount(enumValue<UCHAR_BINARY_LIMIT ? 2 : 0) {}

	// END DATA
	//----------------------------------------------------------------------

	class PNamesPropertyNames : public PropertyNames {
	public:
	PNamesPropertyNames()
	: valueMaps(NULL), bytesTries(NULL) {}
	void init(const int32_t vm, const uint8_t bt) {
	valueMaps=vm;
	bytesTries=bt;
	}
	virtual int32_t getPropertyEnum(const char *name) const;
	virtual int32_t getPropertyValueEnum(int32_t property, const char *name) const;
	private:
	int32_t findProperty(int32_t property) const;
	UBool containsName(BytesTrie &trie, const char *name) const;
	int32_t getPropertyOrValueEnum(int32_t bytesTrieOffset, const char *alias) const;

	const int32_t *valueMaps;
	const uint8_t *bytesTries;
	};

	class PNamesBuilderImpl : public PNamesBuilder {
	public:
	PNamesBuilderImpl(UErrorCode &errorCode)
	: valueMaps(errorCode), btb(errorCode), maxNameLength(0),
	nameGroupToOffset(NULL) {}

	~PNamesBuilderImpl() {
	uhash_close(nameGroupToOffset);
	}

	virtual void build(UErrorCode &errorCode) {
	if(U_FAILURE(errorCode)) { return; }
	if(VALUE_MAX_ALIASES<MAX_ALIASES) {
	fprintf(stderr,
	"genprops error: pnamesbuilder.cpp VALUE_MAX_ALIASES=%d<%d=MAX_ALIASES -- "
	"need to change VALUE_MAX_ALIASES to at least %d\n",
	(int)VALUE_MAX_ALIASES, (int)MAX_ALIASES, (int)MAX_ALIASES);
	errorCode=U_INTERNAL_PROGRAM_ERROR;
	return;
	}
	nameGroupToOffset=uhash_open(uhash_hashChars, uhash_compareChars, NULL, &errorCode);
	// Build main property aliases value map at value map offset 0,
	// so that we need not store another offset for it.
	UVector32 propEnums(errorCode);
	int32_t propIndex;
	for(propIndex=0; propIndex<LENGTHOF(PROPERTIES); ++propIndex) {
	propEnums.sortedInsert(PROPERTIES[propIndex].enumValue, errorCode);
	}
	int32_t ranges[10][2];
	int32_t numPropRanges=uprv_makeDenseRanges(propEnums.getBuffer(),
	LENGTHOF(PROPERTIES), 0x100,
	ranges, LENGTHOF(ranges));
	valueMaps.addElement(numPropRanges, errorCode);
	int32_t i, j;
	for(i=0; i<numPropRanges; ++i) {
	valueMaps.addElement(ranges[i][0], errorCode);
	valueMaps.addElement(ranges[i][1]+1, errorCode);
	for(j=ranges[i][0]; j<=ranges[i][1]; ++j) {
	// Reserve two slots per property for the name group offset and the value-map offset.
	valueMaps.addElement(0, errorCode);
	valueMaps.addElement(0, errorCode);
	}
	}

	// Build the properties trie first, at BytesTrie offset 0,
	// so that we need not store another offset for it.
	buildPropertiesBytesTrie(PROPERTIES, LENGTHOF(PROPERTIES), errorCode);

	// Build the name group for the first property, at nameGroups offset 0.
	// Name groups for value aliases must not start at offset 0
	// because that is a missing-value marker for sparse value ranges.
	setPropertyInt(PROPERTIES[0].enumValue, 0,
	writeValueAliases(PROPERTIES[0], errorCode));

	// Build the known-repeated binary properties once.
	int32_t binPropsValueMapOffset=valueMaps.size();
	int32_t bytesTrieOffset=buildValuesBytesTrie(VALUES_binprop, 2, errorCode);
	valueMaps.addElement(bytesTrieOffset, errorCode);
	buildValueMap(VALUES_binprop, 2, errorCode);

	// Note: It is slightly wasteful to store binary properties like all others.
	// Since we know that they are in the lowest range of property enum values
	// and share the same name group and BytesTrie,
	// we could just store those two indexes once.
	// (This would save 8 bytes per binary property, or about half a kilobyte.)

	// Build the known-repeated canonical combining class properties once.
	int32_t cccValueMapOffset=valueMaps.size();
	bytesTrieOffset=buildValuesBytesTrie(VALUES_ccc, LENGTHOF(VALUES_ccc), errorCode);
	valueMaps.addElement(bytesTrieOffset, errorCode);
	buildValueMap(VALUES_ccc, LENGTHOF(VALUES_ccc), errorCode);

	// Build the rest of the data.
	for(propIndex=0; propIndex<LENGTHOF(PROPERTIES); ++propIndex) {
	if(propIndex>0) {
	// writeValueAliases(PROPERTIES[0], ...) already done
	setPropertyInt(PROPERTIES[propIndex].enumValue, 0,
	writeValueAliases(PROPERTIES[propIndex], errorCode));
	}
	int32_t valueCount=PROPERTIES[propIndex].valueCount;
	if(valueCount>0) {
	int32_t valueMapOffset;
	const Value *values=PROPERTIES[propIndex].values;
	if(values==VALUES_binprop) {
	valueMapOffset=binPropsValueMapOffset;
	} else if(values==VALUES_ccc \|\| values==VALUES_lccc \|\| values==VALUES_tccc) {
	valueMapOffset=cccValueMapOffset;
	} else {
	valueMapOffset=valueMaps.size();
	bytesTrieOffset=buildValuesBytesTrie(values, valueCount, errorCode);
	valueMaps.addElement(bytesTrieOffset, errorCode);
	buildValueMap(values, valueCount, errorCode);
	}
	setPropertyInt(PROPERTIES[propIndex].enumValue, 1, valueMapOffset);
	}
	}

	// Write the indexes.
	int32_t offset=(int32_t)sizeof(indexes);
	indexes[PropNameData::IX_VALUE_MAPS_OFFSET]=offset;
	offset+=valueMaps.size()*4;
	indexes[PropNameData::IX_BYTE_TRIES_OFFSET]=offset;
	offset+=bytesTries.length();
	indexes[PropNameData::IX_NAME_GROUPS_OFFSET]=offset;
	offset+=nameGroups.length();
	for(i=PropNameData::IX_RESERVED3_OFFSET; i<=PropNameData::IX_TOTAL_SIZE; ++i) {
	indexes[i]=offset;
	}
	indexes[PropNameData::IX_MAX_NAME_LENGTH]=maxNameLength;
	for(i=PropNameData::IX_RESERVED7; i<PropNameData::IX_COUNT; ++i) {
	indexes[i]=0;
	}

	if(!beQuiet) {
	puts("* pnames.icu stats *");
	printf("length of all value maps: %6ld\n", (long)valueMaps.size());
	printf("length of all BytesTries: %6ld\n", (long)bytesTries.length());
	printf("length of all name groups: %6ld\n", (long)nameGroups.length());
	printf("length of pnames.icu data: %6ld\n", (long)indexes[PropNameData::IX_TOTAL_SIZE]);
	}
	}

	virtual void writeCSourceFile(const char *path, UErrorCode &errorCode);
	virtual void writeBinaryData(const char *path, UBool withCopyright, UErrorCode &errorCode);

	int32_t writeValueAliases(const Value &value, UErrorCode &errorCode) {
	int32_t nameOffset=uhash_geti(nameGroupToOffset, (void *)value.joinedAliases);
	if(nameOffset!=0) {
	// The same list of aliases has been written already.
	return nameOffset-1; // Was incremented to reserve 0 for "not found".
	}
	// Write this not-yet-seen list of aliases.
	nameOffset=nameGroups.length();
	uhash_puti(nameGroupToOffset, (void *)value.joinedAliases,
	nameOffset+1, &errorCode);
	// The first byte tells us how many aliases there are.
	// We use only values 0..0x1f in the first byte because when we write
	// the name groups as an invariant-character string into a source file,
	// those values (C0 control codes) are written as numbers rather than as characters.
	int32_t count=value.count;
	if(count>=0x20) {
	fprintf(stderr, "Error: Too many aliases in \"%s\"\n", value.joinedAliases);
	exit(U_INDEX_OUTOFBOUNDS_ERROR);
	}
	nameGroups.append((char)count, errorCode);
	// There is at least a short name (sometimes empty) and a long name. (count>=2)
	// Note: Sometimes the short and long names are the same.
	// In such a case, we could set a flag and omit the duplicate,
	// but that would save only about 1.35% of total data size (Unicode 6.0/ICU 4.6)
	// which is not worth the trouble.
	// Note: In Unicode 6.1, there are more duplicates due to newly added
	// short names for blocks and other properties.
	// It might now be worth changing the data structure.
	for(int32_t i=0; i<count; ++i) {
	const char *s=value.aliases[i];
	int32_t sLength=uprv_strlen(s)+1;
	if(sLength>maxNameLength) {
	maxNameLength=sLength;
	}
	nameGroups.append(s, sLength, errorCode); // including NUL
	}
	return nameOffset;
	}

	void buildValueMap(const Value values[], int32_t length, UErrorCode &errorCode) {
	UVector32 sortedValues(errorCode);
	UVector32 nameOffsets(errorCode); // Parallel to values[].
	int32_t i;
	for(i=0; i<length; ++i) {
	sortedValues.sortedInsert(values[i].enumValue, errorCode);
	nameOffsets.addElement(writeValueAliases(values[i], errorCode), errorCode);
	}
	int32_t ranges[10][2];
	int32_t numRanges=uprv_makeDenseRanges(sortedValues.getBuffer(), length, 0xe0,
	ranges, LENGTHOF(ranges));
	if(numRanges>0) {
	valueMaps.addElement(numRanges, errorCode);
	for(i=0; i<numRanges; ++i) {
	valueMaps.addElement(ranges[i][0], errorCode);
	valueMaps.addElement(ranges[i][1]+1, errorCode);
	for(int32_t j=ranges[i][0]; j<=ranges[i][1]; ++j) {
	// The range might not be completely dense, so j might not have an entry,
	// in which case we write a nameOffset of 0.
	// Real nameOffsets for property values are never 0.
	// (The first name group is for the first property name.)
	int32_t valueIndex=valuesIndexOf(values, length, j);
	int32_t nameOffset= valueIndex>=0 ? nameOffsets.elementAti(valueIndex) : 0;
	valueMaps.addElement(nameOffset, errorCode);
	}
	}
	} else {
	// No dense ranges.
	valueMaps.addElement(0x10+length, errorCode);
	for(i=0; i<length; ++i) {
	valueMaps.addElement(sortedValues.elementAti(i), errorCode);
	}
	for(i=0; i<length; ++i) {
	valueMaps.addElement(
	nameOffsets.elementAti(
	valuesIndexOf(values, length,
	sortedValues.elementAti(i))), errorCode);
	}
	}
	}

	static int32_t valuesIndexOf(const Value values[], int32_t length, int32_t value) {
	for(int32_t i=0;; ++i) {
	if(values[i].enumValue==value) {
	return i;
	}
	}
	return -1;
	}

	void setPropertyInt(int32_t prop, int32_t subIndex, int32_t value) {
	// Assume that prop is in the valueMaps.elementAti(0) ranges.
	int32_t index=1;
	for(;;) {
	int32_t rangeStart=valueMaps.elementAti(index);
	int32_t rangeLimit=valueMaps.elementAti(index+1);
	index+=2;
	if(rangeStart<=prop && prop<rangeLimit) {
	valueMaps.setElementAt(value, index+2*(prop-rangeStart)+subIndex);
	break;
	}
	index+=2*(rangeLimit-rangeStart);
	}
	}

	void addValueToBytesTrie(const Value &value, UErrorCode &errorCode) {
	const char *aliases[MAX_ALIASES];
	int32_t numAliases=value.getUniqueNormalizedAliases(aliases);
	for(int32_t i=0; i<numAliases; ++i) {
	btb.add(aliases[i], value.enumValue, errorCode);
	}
	}

	int32_t buildValuesBytesTrie(const Value values[], int32_t length, UErrorCode &errorCode) {
	btb.clear();
	for(int32_t i=0; i<length; ++i) {
	addValueToBytesTrie(values[i], errorCode);
	}
	int32_t bytesTrieOffset=bytesTries.length();
	bytesTries.append(btb.buildStringPiece(USTRINGTRIE_BUILD_SMALL, errorCode), errorCode);
	return bytesTrieOffset;
	}

	// Variant of buildValuesBytesTrie() for Property.
	// Property is-a Value, and the source code is the same,
	// but when we iterate through the array we need to increment by the right object size.
	int32_t buildPropertiesBytesTrie(const Property properties[], int32_t length,
	UErrorCode &errorCode) {
	btb.clear();
	for(int32_t i=0; i<length; ++i) {
	addValueToBytesTrie(properties[i], errorCode);
	}
	int32_t bytesTrieOffset=bytesTries.length();
	bytesTries.append(btb.buildStringPiece(USTRINGTRIE_BUILD_SMALL, errorCode), errorCode);
	return bytesTrieOffset;
	}

	virtual const PropertyNames *getPropertyNames() {
	pnames.init(valueMaps.getBuffer(),
	reinterpret_cast<const uint8_t *>(bytesTries.data()));
	return &pnames;
	}

	private:
	int32_t indexes[PropNameData::IX_COUNT];
	UVector32 valueMaps;
	BytesTrieBuilder btb;
	CharString bytesTries;
	CharString nameGroups;
	int32_t maxNameLength;
	PNamesPropertyNames pnames;
	UHashtable *nameGroupToOffset;
	};

	/* UDataInfo cf. udata.h */
	static const UDataInfo dataInfo = {
	sizeof(UDataInfo),
	0,

	U_IS_BIG_ENDIAN,
	U_CHARSET_FAMILY,
	sizeof(UChar),
	0,

	{ PNAME_SIG_0, PNAME_SIG_1, PNAME_SIG_2, PNAME_SIG_3 },
	{ 2, 0, 0, 0 }, /* formatVersion */
	UNICODE_VERSION
	};

	void
	PNamesBuilderImpl::writeBinaryData(const char *path, UBool withCopyright, UErrorCode &errorCode) {
	if(U_FAILURE(errorCode)) { return; }
	UNewDataMemory *pdata=udata_create(path, PNAME_DATA_TYPE, PNAME_DATA_NAME, &dataInfo,
	withCopyright ? U_COPYRIGHT_STRING : 0, &errorCode);
	if(U_FAILURE(errorCode)) {
	fprintf(stderr, "genprops: udata_create(%s, pnames.icu) failed - %s\n",
	path, u_errorName(errorCode));
	return;
	}

	udata_writeBlock(pdata, indexes, PropNameData::IX_COUNT*4);
	udata_writeBlock(pdata, valueMaps.getBuffer(), valueMaps.size()*4);
	udata_writeBlock(pdata, bytesTries.data(), bytesTries.length());
	udata_writeBlock(pdata, nameGroups.data(), nameGroups.length());

	int32_t dataLength=(int32_t)udata_finish(pdata, &errorCode);
	if(dataLength!=indexes[PropNameData::IX_TOTAL_SIZE]) {
	fprintf(stderr,
	"udata_finish(pnames.icu) reports %ld bytes written but should be %ld\n",
	(long)dataLength, (long)indexes[PropNameData::IX_TOTAL_SIZE]);
	errorCode=U_INTERNAL_PROGRAM_ERROR;
	}
	}

	void
	PNamesBuilderImpl::writeCSourceFile(const char *path, UErrorCode &errorCode) {
	if(U_FAILURE(errorCode)) { return; }
	FILE *f=usrc_create(path, "propname_data.h",
	"icu/tools/unicode/c/genprops/pnamesbuilder.cpp");
	if(f==NULL) {
	errorCode=U_FILE_ACCESS_ERROR;
	return;
	}

	fputs("#ifndef INCLUDED_FROM_PROPNAME_CPP\n"
	"# error This file must be #included from propname.cpp only.\n"
	"#endif\n\n", f);

	fputs("U_NAMESPACE_BEGIN\n\n", f);

	usrc_writeArray(f, "const int32_t PropNameData::indexes[%ld]={",
	indexes, 32, PropNameData::IX_COUNT,
	"};\n\n");
	usrc_writeArray(f, "const int32_t PropNameData::valueMaps[%ld]={\n",
	valueMaps.getBuffer(), 32, valueMaps.size(),
	"\n};\n\n");
	usrc_writeArray(f, "const uint8_t PropNameData::bytesTries[%ld]={\n",
	bytesTries.data(), 8, bytesTries.length(),
	"\n};\n\n");
	usrc_writeArrayOfMostlyInvChars(
	f, "const char PropNameData::nameGroups[%ld]={\n",
	nameGroups.data(), nameGroups.length(),
	"\n};\n\n");

	fputs("U_NAMESPACE_END\n", f);

	fclose(f);
	}

	PNamesBuilder *
	createPNamesBuilder(UErrorCode &errorCode) {
	if(U_FAILURE(errorCode)) { return NULL; }
	PNamesBuilder *pb=new PNamesBuilderImpl(errorCode);
	if(pb==NULL) {
	errorCode=U_MEMORY_ALLOCATION_ERROR;
	}
	return pb;
	}

	// Note: The following is a partial copy of runtime propname.cpp code.
	// Consider changing that into a semi-public API to avoid duplication.

	int32_t PNamesPropertyNames::findProperty(int32_t property) const {
	int32_t i=1; // valueMaps index, initially after numRanges
	for(int32_t numRanges=valueMaps[0]; numRanges>0; --numRanges) {
	// Read and skip the start and limit of this range.
	int32_t start=valueMaps[i];
	int32_t limit=valueMaps[i+1];
	i+=2;
	if(property<start) {
	break;
	}
	if(property<limit) {
	return i+(property-start)*2;
	}
	i+=(limit-start)*2; // Skip all entries for this range.
	}
	return 0;
	}

	UBool PNamesPropertyNames::containsName(BytesTrie &trie, const char *name) const {
	if(name==NULL) {
	return FALSE;
	}
	UStringTrieResult result=USTRINGTRIE_NO_VALUE;
	char c;
	while((c=*name++)!=0) {
	c=uprv_invCharToLowercaseAscii(c);
	// Ignore delimiters '-', '_', and ASCII White_Space.
	if(c==0x2d \|\| c==0x5f \|\| c==0x20 \|\| (0x09<=c && c<=0x0d)) {
	continue;
	}
	if(!USTRINGTRIE_HAS_NEXT(result)) {
	return FALSE;
	}
	result=trie.next((uint8_t)c);
	}
	return USTRINGTRIE_HAS_VALUE(result);
	}

	int32_t PNamesPropertyNames::getPropertyOrValueEnum(int32_t bytesTrieOffset, const char *alias) const {
	BytesTrie trie(bytesTries+bytesTrieOffset);
	if(containsName(trie, alias)) {
	return trie.getValue();
	} else {
	return UCHAR_INVALID_CODE;
	}
	}

	int32_t
	PNamesPropertyNames::getPropertyEnum(const char *alias) const {
	return getPropertyOrValueEnum(0, alias);
	}

	int32_t
	PNamesPropertyNames::getPropertyValueEnum(int32_t property, const char *alias) const {
	int32_t valueMapIndex=findProperty(property);
	if(valueMapIndex==0) {
	return UCHAR_INVALID_CODE; // Not a known property.
	}
	valueMapIndex=valueMaps[valueMapIndex+1];
	if(valueMapIndex==0) {
	return UCHAR_INVALID_CODE; // The property does not have named values.
	}
	// valueMapIndex is the start of the property's valueMap,
	// where the first word is the BytesTrie offset.
	return getPropertyOrValueEnum(valueMaps[valueMapIndex], alias);
	}