Internationalization for the NFSv4 Protocols

2.1. Requirements Language Definition

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as BCP 14 [1] [2] when, and only when, they appear in all capitals, as shown here.¶

2.2. Requirements Language Derivation

Although the key words "MUST", "SHOULD", and "MAY" retain their normal meanings, as described above, we need to explain how the statements involving these terms were arrived at:¶

• In the case of statements within Sections 12 and 15, these derive from the requirements of other internet specifications.¶
• In the case of statements within Sections 7, 10, and 11 derive from the author's view of the appropriate normative language to use and will, when this document is advanced, represent the working group's consensus on those same matters.¶
• However, in other cases, i.e. those in sections deriving from RFC7530 [3] (i.e. Sections 5, 6, 8, 9, 13, 14, 16, 17) this specification's descriptions were derived from existing implementation patterns. Although this pattern is atypical, it is needed to provide a description that satisfies the goal of RFC2119 [1], providing a normative description to enable future implementations to be compatible with existing ones. This requires that we explain later in this section how the normative terms used derive from the behavior of existing implementations, in those situations in which existing implementation behavior patterns can be determined.¶

Note that in introductory and explanatory sections of this document (i.e. Sections 1 through 4 these terms do not appear except to explain how they are used in this document. Also, they do not appear in Appendix A which provides non-normative implementation guidance.¶

With regard to the parts of this document deriving from RFC7530, we explain below how the normative terms used derive from the behavior of existing implementations, in those situations in which existing implementation behavior patterns can be determined.¶

• Behavior implemented by all existing clients or servers is described using "MUST", since new implementations need to follow existing ones to be assured of interoperability. While it is possible that different behavior might be workable, we have found no case where this seems reasonable.¶

  The converse holds for "MUST NOT": if a type of behavior poses interoperability problems, it MUST NOT be implemented by any existing clients or servers.¶

• Behavior implemented by most existing clients or servers, where that behavior is more desirable than any alternative, is described using "SHOULD", since new implementations need to follow that existing practice unless there are strong reasons to do otherwise.¶

  The converse holds for "SHOULD NOT".¶

• Behavior implemented by some, but not all, existing clients or servers is described using "MAY", indicating that new implementations have a choice as to whether they will behave in that way. Thus, new implementations will have the same flexibility that existing ones do.¶
• Behavior implemented by all existing clients or servers, so far as is known -- but where there remains some uncertainty as to details -- is described using "should". Such cases primarily concern details of error returns. New implementations should follow existing practice even though such situations generally do not affect interoperability.¶

There are also cases in which certain server behaviors, while not known to exist, cannot be reliably determined not to exist. In part, this is a consequence of the long period of time that has elapsed since the publication of the defining specifications, resulting in a situation in which those involved in t implementation work may no longer be involved in or aware of working group activities.¶

In the case of possible server behavior that is neither known to exist nor known not to exist, we use "SHOULD NOT" and "MUST NOT" as follows, and similarly for "SHOULD" and "MUST".¶

• In some cases, the potential behavior is not known to exist but is of such a nature that, if it were in fact implemented, interoperability difficulties would be expected and reported, giving us cause to conclude that the potential behavior is not implemented. For such behavior, we use "MUST NOT". Similarly, we use "MUST" to apply to the contrary behavior.¶
• In other cases, potential behavior is not known to exist but the behavior, while undesirable, is not of such a nature that we are able to draw any conclusions about its potential existence. In such cases, we use "SHOULD NOT". Similarly, we use "SHOULD" to apply to the contrary behavior.¶

In the case of a "MAY", "SHOULD", or "SHOULD NOT" that applies to servers, clients need to be aware that there are servers that may or may not take the specified action, and they need to be prepared for either eventuality.¶

7.1. The Attribute Fs_charset_cap in Published NFSv4.1 Specifications

We reproduce Section 14.4 of [10] below, with comments interspersed trying to make sense of what is there, in order to arrive at an appropriate replacement, to be presented in Section 7.2. In that connection, we need to understand better a few issues:¶

• The use of two bits while one is clearly adequate, given the subject matter actually mentioned¶
• The mention of possible "capabilities" which could not possibly be realized.¶
• The use of the RFC2119 keyword "SHOULD" in contexts in which this term is clearly inappropriate.¶

Issues related to the confusion caused by mention of "UTF-8 characters" and the lack of mention of Unicode will be addressed in the revision in Section 7.2 but will not be further discussed here.¶

   const FSCHARSET_CAP4_CONTAINS_NON_UTF8  = 0x1;
   const FSCHARSET_CAP4_ALLOWS_ONLY_UTF8   = 0x2;

   typedef uint32_t        fs_charset_cap4;

While it is made clear that two separate bits are to be provided, their names seem to indicate that they should be complements of one another. As a way of understanding why two bits were specified, it is helpful to consider a possible boolean attribute as a potential replacement. That attribute would clearly govern whether names that do not conform to the rules of UTF-8 are to be rejected, which was a "MUST" in RFC3530 [21]. Although conveying this information is clearly part of the motivation, stating so clearly might have been judged by the authors as too provocative, given the role of IESG in arriving at the internationalization approach specified in RFC3530.¶

• Because some operating environments and file systems do not enforce character set encodings,¶

It is clear that the ability of operating environments to enforce use of UTF-8 encoding is not an issue, since RFC3530 made this the responsibility of the server implementation. That mandate was never followed because implementers chose not to follow it, and not because they were unable to do so. The apparently confused statement above is best understood if one notes that its essential job is to state that the "MUST" in RFC3530 referred to above is not reasonable. However, the authors might well feel unable to say so clearly, in light of the potential IESG reaction.¶

• NFSv4.1 supports the fs_charset_cap attribute (Section 5.8.2.11) that indicates to the client a file system's UTF-8 capabilities.¶

The problem with the mention of (plural) capabilities is that the only capability mentioned which servers could implement is to accept strings which are not valid UTF-8. There are other potential capabilities having to do with the implementation of canonical equivalence, but since they were not mentioned, they will not be discussed further here.¶

• The attribute is an integer containing a pair of flags. The first flag is FSCHARSET_CAP4_CONTAINS_NON_UTF8, which, if set to one, tells the client that the file system contains non-UTF-8 characters,¶

As stated, this would mean that a server would have to keep track of a count of non-UTF-8-encoded names within the file system and change the attribute value as that count varied between zero and non-zero. Since it is most unlikely that any server would keep track of that or that any client would find it useful, we will assume that the capability to store such names is what is most likely intended.¶

• and the server will not convert non-UTF characters to UTF-8 if the client reads a symbolic link or directory,¶

There is no way for the server to convert non-UTF names to UTF-8 or anything else, since it has no knowledge of the name encoding to begin with. The alternative to treating names as UTF-8-encoded Unicode strings is to treat them as POSIX does, as uninterpreted strings of bytes. That makes it impossible to interpret strings that do not follow the rules of UTF-8 at all, making it impossible to convert the string to UTF-8.¶

• neither will operations with component names or pathnames in the arguments convert the strings to UTF-8.¶

As stated above, there is no way a server could ever do that.¶

• The second flag is FSCHARSET_CAP4_ALLOWS_ONLY_UTF8, which, if set to one, indicates that the server will accept (and generate) only UTF-8 characters on the file system.¶

That is clear and so it poses no problem for a revised treatment, unlike the other flag.¶

• If FSCHARSET_CAP4_ALLOWS_ONLY_UTF8 is set to one, FSCHARSET_CAP4_CONTAINS_NON_UTF8 MUST be set to zero.¶

There is no problem with this statement. However, it does, by implication, raise the issue of what values of FSCHARSET_CAP4_CONTAINS_NON_UTF8 may be set in the case in which FSCHARSET_CAP4_ALLOWS_ONLY_UTF8 is set to zero.¶

• FSCHARSET_CAP4_ALLOWS_ONLY_UTF8 SHOULD always be set to one.¶

According to RFC2119 [1], "SHOULD" means that "there may exist valid reasons in particular circumstances to ignore a particular item, but the full implications must be understood and carefully weighing a different course". In this context, it is unclear what these "full implications" might be given the introduction above. The clause, "because some operating e environments and file systems do not enforce character set encodings", gives one no basis for treating this as other than an unproblematic behavior variant, calling into question the use of "SHOULD".¶

Also, the statement in RFC2119 that these terms (i.e. those like "SHOULD") "only be used where it is actually required for interoperation or to limit behavior which has the potential for causing harm"¶

• The whole purpose of this feature is to enable interoperation and there is no basis for the implication that one particular flag value is superior to another in allowing interoperation.¶
• There is no basis for assuming that accepting file names that are not UTF-8-encoded Unicode has any potential for causing harm.¶

Despite the statement in RFC2119, that "they [i.e. terms such as 'SHOULD'] must not be used to impose a particular method on implementors", it is hard to avoid the conclusion that this is in fact the motivation for the "SHOULD", although the authors might not have had any such intention but felt that the IESG might well have such an intention.¶

7.2. The Attribute Fs_charset_cap in Future NFSv4.1 Specifications

We provide a revised version of Section 14.4 of [10] below, taking into account the issues noted in Section 7.1. Given there was a working group consensus to adopt the confusing language discussed there, we must now adopt, by consensus, a clearer replacement that reclects the working group's intentions. Given the passage of time and the changed context, it might not be possible to determine those intentions. In any case, we will have to be aware of how this attribute was implemented and used, particularly with regard to the first flag, whose meaning remains obscure.¶

The following treatment is proposed as a basis for discussion, with the understanding that it needs to be changed, if it raises interoperability issues.¶

   const FSCHARSET_CAP4_CONTAINS_NON_UTF8  = 0x1;
   const FSCHARSET_CAP4_ALLOWS_ONLY_UTF8   = 0x2;

   typedef uint32_t        fs_charset_cap4;

• This attribute provides a simple way of determining whether a particular file system behaves as a UTF-8-only server and rejects file names which are not valid UTF-8 strings. When this attribute is supported and the value returned has the FSCHARSET_CAP4_ALLOWS_ONLY_UTF8 flag set, the error NFS4ERR_INVAL MUST be returned if any file name argument contains a string which is not a valid UTF-8 string.¶
• When this attribute is supported and the value returned has the FSCHARSET_CAP4_ALLOWS_ONLY_UTF8 flag clear, the error NFS4ERR_INVAL will not be returned based on adherence to the rules of UTF-8. While such file systems are generally UTF-8-unaware, this cannot be assumed, since server are allowed (in some circumstances; it is a "SHOULD NOT") to accept non-UTF-8 names while being aware of the structure of UTF-8-conforming names, for the purposes of determining canonical equivalence, for example. See Section 6.¶
• With regard to the flag FSCHARSET_CAP4_CONTAINS_NON_UTF8, it has proved impossible to determine, from existing treatments of this attribute, any value that might be helpful here. As a result, we are forced to assume that this flag is always a complement of FSCHARSET_CAP4_ALLOWS_ONLY_UTF8 and that any result in which it is not is to be ignored, with the appropriate handling being the same as would apply if the attribute were not supported.¶
• When this attribute is not supported, the client can perform a LOOKUP using a name not conforming to the rules of UTF-8 and use the error returned to determine whether non-UTF-8 names are accepted.¶

10.1. Implementing Case-Insensitive Comparison of File Names

Implementing case-insensitive string comparisons based on equivalence classes including multi-character strings can be performed as described below. This algorithm requires that if there is more than one multi-character string within a given equivalence class, they must all be equivalent, with any equivalences derivable from case-insensitive string equivalence using single-character equivalence classes.¶

Although other sources are possible (see items EX2 and EX3 in Section 10.2), multi-character sequences often appear in case-insensitive equivalence classes as the result of the canonical decomposition of one or more precomposed characters as elements of a case-insensitive equivalence class.¶

While the algorithm described in this section can deal with certain case-based equivalences deriving from canonical decomposition, it is not capable of providing general handling of the combination of canonical equivalence and case-based equivalence. While this can be addressed by normalizing strings before doing case-insensitive comparison, it is more efficient to do a general form-insensitive and case-insensitive string comparison in a single step as described in Appendix A¶

The following tables would be used by the comparison algorithm presented below.¶

• For each possible character value, the associated equivalence class for case-insensitive comparison will be identified¶
• For each such equivalence class, the hash value contribution will be provided. In the case of equivalence class that do not include multi-character including equivalence classes that only include a single member, this will be the hash value contribution of one particular variant (usually lower case) of the character¶
• In the case of equivalence classes that do include multi-character strings, the hash value contribution needs to equivalent to the combined contribution of each character within the multi-character string. In addition, for each such equivalence class, the length of the multicharacter string will be provided together with a pointer to an array describing the multi-character string, most probably presenting each character as an equivalence class id.¶

Case-insensitive comparison proceeds as follows:¶

• Implementation of case-insensitive name comparisons will typically require a case-insensitive name hash using the tables described above. If such a hash vale is kept or all cached names comparisons of hashes can be used instead of the detailed comparison set forth below. Using such hash comparisons, a large set of potentially equivalent names can be excluded based on the occurrence of hash mismatches, since case-equivalent names would have the same hash value. value.¶
• For names with matching hash values, a detailed case-insensitive comparison will be necessary. This can proceed character-by- character or byte-by-byte. However, in the byte-by-byte case, processing in the event of a mismatch must start at the start of the current character, rather than the byte at which the difference was detected.¶
• In cases in which there is a mismatch, the associated equivalence classes will be compared. When these are identical, indicating the case equivalence of the two characters, the comparison of the two strings continues at the next character of each string.¶
• When the two equivalence classes are not identical, further comparisons to determine if a single character within one string matches (except for case) a multi-character string within the other. For each of two equivalence classes being compared that include a multi-character string, the check below must be made to determine whether the multi-character string at the corresponding position of the other string being compared, is within the current equivalence class. If neither of the two equivalence classes include multi-character strings, the comparison terminates with a mismatch indication.¶
• For each equivalence class that does include a multi-character string (there might be one or two), a scan needs to be made to see of the characters at the current position if the other string matches (except for case) the multi-character string which is included in the current equivalence class. If this check succeeds, for either equivalence class, the comparison of the two strings continues at the next character of each string. In the event of failure, the same sort of comparison is done using the other current equivalence class, if it include multi-character strings. Once this check fails for all equivalence classes that include multi-character strings, the comparison terminates with a mismatch indication.¶

10.2. Important Examples of Case-insensitive Handling of File Names

In this section, we discuss many of the interesting and/or troublesome issues that the need for case-insensitive handling gives rise to in fully internationalized environment. Many of these are also discussed in [13]. However, our treatment of these issues, while not inconsistent with that in [13], differs significantly for a number of reasons:¶

• Our primary focus is on case-insensitive string comparison rather than with case mapping per se. While such comparison is natural for the client and allowed for servers, its greater flexibility makes it important to understand its capabilities in dealing with potentially troublesome issues in providing case-insensitive file name handling.¶
• Because a case mapping model forces the specification of a single case mapping result when there are multiple potentially valid results, there are inevitably cases in which the result chosen is is inappropriate for some users. These are cases in which F-type and S-type mappings are present and in which C-type and T-type mappings conflict. Normally, an appropriate choice is selected by use of the locale, but in a filesystem environment, valid locale information might not be present. As a result, case-insensitive string comparison, which does not force such case mapping choices, will be more desirable.¶

The examples below present common situations that go beyond the simple invertible case mappings of Latin characters and the straightforward adaptation of that model to Greek and Cyrillic. In EX4 and EX5 we have case-based equivalence classes including multi-character strings not derived from canonical equivalences while for EX7 and EX8 all multi-character strings are derived from canonical equivalences. In addition, EX1, EX2, EX3 and EX6 discuss other situations in which an equivalence class has more than two elements.¶

EX1:

Certain digraph characters such LATIN SMALL LETTER DZ (U+01F3) have additional case variants to consider such as the titlecase character LATIN CAPTAL LETTER D WITH SMALL LETTER Z (U+01F2) in addition to the uppercase LATIN CAPITAL LETTER DZ (U+01F1). While the titlecased variant would not appear in names in case-insensitive non-case-preserving file systems, case-insensitive string comparison has no problem in treating these three characters as within the same equivalence class.¶

This equivalence class can be derived from only C-type mappings. The possibility of mapping these characters to two-character sequences they represent is not a troublesome issue since that would be derived from a compatibility equivalence, rather than a canonical equivalence, and there is no F-type mapping making it an option.¶

EX2:

To deal with the case of the OHM SIGN (U+2126) which is essentially identical to the GREEK CAPITAL LETTER OMEGA (U+03A9), one can construct an equivalence class consisting of OHM SIGN (U+2126), GREEK CAPITAL LETTER OMEGA (U+03A9), and GREEK SMALL LETTER OMEGA (U+03C9).¶

This equivalence class can be derived only from C-type mappings. Both OHM SIGN (U+2126), and GREEK CAPITAL LETTER OMEGA (U+03A9) lowercase to GREEK LETTER OMEGA (U+03C9), while that character only uppercases to GREEK CAPITAL LETTER OMEGA (U+03A9).¶

EX3:

To deal with the case of the ANGSTROM SIGN (U+212B) which is essentially identical to LATIN CAPITAL LETTER A WITH RING ABOVE (U+00C5), one can construct an equivalence class consisting of ANGSTROM SIGN (U+212B), LATIN CAPITAL LETTER A WITH RING ABOVE (U+00C5), LATIN SMALL LETTER A WITH RING ABOVE (U+00E5), together with the two-character sequences involving LATIN CAPITAL LETTER A (U+0041) or LATIN SMALL LETTER A (U+0061) followed by COMBINING RING ABOVE (U+030A).¶

This equivalence class can be derived from C-type mappings together with the ability to map characters to canonically equivalent strings. Both ANGSTROM SIGN (U+212B), and LATIN CAPITAL LETTER A WITH RING ABOVE (U+00C5) lowercase to LATIN SMALL LETTER A WITH RING ABOVE (U+00E5), while that character only uppercases to CAPITAL LETTER A WITH RING ABOVE (U+00C5).¶

EX4:

In some cases, case mapping of a single character will result in a multi-character string. For example, the German character LATIN SMALL LETTER SHARP S (U+00DF) would be uppercased to "SS", i.e. two copies of LATIN CAPITAL LETTER S (U+0053). On the other hand, in some situations, it would be uppercased to the character LATIN CAPITAL LETTER SHARP S (U+1E9E), using an S-type mapping. referred to as an instance of "Tailored Casing". Unfortunately, in the context of a file system, there is unlikely to be available information that provides guidance about which of these case mappings should be chosen. However, the use of case-insensitive mappings with larger equivalence classes often provides handling that is acceptable to a wider variety of users. In this case, German-speakers get the mapping they expect while those unfamiliar with these characters only see them when they access a file whose name contains them.¶

It appears that if the construction of case-based equivalence classes were generalized to include multi-character sequences, then all of LATIN SMALL LETTER SHARP S (U+00DF), LATIN CAPITAL LETTER SHARP S (U+1E9E), "ss", "sS", "Ss", and "SS" would belong to the same equivalence class and could be handled by the general algorithm described in Section 10.1, as well by code specifically written to deal with this particular issue.¶

EX5:

Other ligatures, such as LATIN SMALL LIGATURE FFL (U+FB04), could be handled similarly by this algorithm, if there were felt a need to do so. However, because the decomposition of this character into the string consisting of the three letters LATIN SMALL LETTER F (U+0066), LATIN SMALL LETTER F (U+0066), LATIN SMALL LETTER L (U+006C), is a compatibility equivalence, and the F-type mapping of this ligature to the three constituent is to be treated as optional, implementations can choose either to treat this character as having no uppercase equivalent or treat it as part of larger equivalence class including "ffl", "ffL", "fFl", etc.).¶

EX6:

The character COMBINING GREEK YPOGEGRAMMENI (U+0345), also known as "iota-subscript" requires special handling when uppercasing and lowercasing. While the description of the appropriate handling for this character, in the case mapping section, is focused on multi- character sequences representing diphthongs, case-insensitive comparisons can be performed without consideration of multi-character sequences. This can be done by assigning COMBINING GREEK YPOGEGRAMMENI (U+0345), GREEK SMALL LETTER IOTA (U+03B9), and GREEK CAPITAL LETTER IOTA (U+0399) to the same equivalence class, even though the first of these is a combining character and the others are not.¶

EX7:

In some cases context-dependent case mapping is required. For example, GREEK CAPITAL LETTER SIGMA (U+03A3) lowercases to GREEK SMALL LETTER SIGMA (U+03C3) if it is followed by another letter and to GREEK SMALL LETTER FINAL SIGMA (U+03C2) if it is not.¶

Despite this, case-insensitive comparisons can be implemented, by considering all of these characters as part of the same equivalence class, without any context-dependence, and this equivalence class can be derived using only C-type mappings.¶

EX8:

In most languages written using Latin characters, the uppercase and lowercase varieties of the letter "I" differ in that only the lowercase character. In a number of Turkic languages, there are two distinct characters derived from "I" which differ only with regard to the presence or absence of a dot so that there are both capital and small i's with each having dotted and dotless variants. Within such languages, the dotted and dotless I's represent different vowel sounds and are treated as separate characters with respect to case mapping. The uppercase of LATIN SMALL LETTER I (U+0069) is LATIN CAPITAL LETTER I WITH DOT ABOVE (U+0130), rather than LATIN CAPITAL LETTER I (U+0049). Similarly the lowercase of LATIN CAPITAL LETTER I (U+0049) is LATIN SMALL LETTER DOTLESS I (U+0131) rather than LATIN SMALL LETTER I (U+0069).¶

When doing case mapping, the server must choose to uppercase LATIN SMALL LETTER I (U+0069) to either LATIN CAPITAL LETTER I (U+0049), based on a C-type mapping to LATIN CAPITAL LETTER I WITH DOT ABOVE (U+0130), based on a T-type mapping. The former is acceptable to most people but confusing to speakers of the Turkic languages in question since the case mapping changes the character to represent a different vowel sound. On the other hand, the latter mapping seemingly inexplicably results in a character many users have never seen before. Normally such choices are dealt with based on a locale but, in a file system environment, no locale information may be available.¶

In the context of case-insensitive string comparison, it is possible to create a larger equivalence class, including all of the letters LATIN SMALL LETTER I (U+0069), LATIN CAPITAL LETTER I (U+0049), LATIN CAPITAL LETTER I WITH DOT ABOVE (U+0130), LATIN SMALL LETTER DOTLESS I (U+0131) together with the two-character string consisting of LATIN CAPITAL LETTER I (U+0049) followed by COMBINING DOT ABOVE (U+0307).¶

11.1. Server Restrictions to Deal with Lack of Client Knowledge

There are a number of restrictions, not previously specified in RFC7530 [3], on server implementation of internationalized file name handling. These restrictions apply to both case-sensitive and case-insensitive file systems and are designed to limit the options that servers have in choosing server-side internationalized file name handling so as to enable the clients to either duplicate that handling or limit it to avoid relying on cases in which the proper handling cannot be determined or duplicated by the client.¶

• The canonical equivalence relation implemented by the server, for each internationalization-aware filesystem MUST match that defined by some particular UNICODE version equal to or later than version 4.0.¶
• The case-equivalence relationship implemented by the server, for each case-insensitive filesystem MUST include all C-type case mappings included by the particular UNICODE version whose canonical equivalence relation is implemented by the server, with the possible exception of those conflicting with T-type case mappings. by some particular Unicode version equal to or later than version 4.0.¶

• In cases in which the server provides no way of determining the details of the case-equivalence relationship implemented by the server for a particular file system, that mapping must include all C-type case mappings included by the particular UNICODE version whose canonical equivalence relation is implemented by the server, i.e. it MUST map between LATIN SMALL LETTER I (U+0069)and LATIN CAPITAL LETTER I (U+0049).¶

11.2. Client Processing of File Names for Current NFSv4 Protocols

The existing minor versions, NFSv4.0 [3], NFSv4.1 [4], and NFSv4.2 [5], have very limited facilities allowing a client to get information about the server's internationalization-related file name handling. Because these protocols were all defined when it was assumed that the server's internationalized file name handling could be specified in great detail, there was no provision for attributes defining the server's choices. As a result, the information available to the client is quite limited:¶

• The client can determine that the server is not performing internationalized file name processing. It can do this by looking up a file name using a string which is not valid UTF-8, concluding that if the LOOKUP is not rejected on that basis, then the file system is not internationalization-aware, allowing the client to ignore the potential difficulties which server-based internationalized file name processing might give rise to.¶
• The client can use the optional per-fs attributes case_insensitive and case_preserving to how the server deals with character case for particular file system. When one of these attributes is not supported by a particular file system, the client treats the attribute as if it were false.¶

When a file system is internationalization-unaware, the client can use both positive and negative name caching, without any issues arising from the potential for conflict between distinct file names that would be considered equivalent by the server. In other cases, the handling is more restricted in the use of negative name caching. The issue with regard to case-sensitive and case-insensitive file systems are discussed separately below. In each case, the client has a range of choices trading off forgone optimization opportunities against the difficulty of implementation while avoiding negative consequences arising from the fact that certain details of the server's name handling are not known to it.¶

In the case of case-sensitive file systems, the uncertainty to be dealt with concerns the version of Unicode implemented by the server, given that different versions may have different canonical equivalence relationships. However, whether the server implements a particular normalization form or implements form-insensitive file name matching has no effect on client behavior. In light of the uncertainty created by the lack of knowledge of the precise Unicode version used by the server to implement its canonical equivalence relation, the follow possibilities, arranged in order of increasing value (and difficulty of implementation) should be considered.¶

A1:

The client can simply decline to implement optimizations based on negative name caching on internationalization-aware file systems.¶

While this might have a negative effect on performance, it might be the best option for clients not heavily used to access internationalization-aware filesystems, or where, due to a lack of directory delegation support, the client has no assurance that will be notified of the invalidation of a previous assumption that a particular file does not exist.¶

A2:

Relatively simple name filtering can exclude the names for which negative name caching might cause difficulties. For example, the client could scan file names for characters whose presence might pose difficulties and allow negative name caching only for strings known not to contain such characters. Because the Unicode version used by the server file system is not known, this treatment would be limited to string only containing characters defined in the earliest version of Unicode which could be supported, that is, Unicode 4.0.¶

One simple way for a client to provide such filtering would be to establish an upper limit (e.g. U+00ff) and disallow negative name caching for strings containing characters above that value or characters below that value that might cause there to be canonically equivalent strings on the server. A simple mask could be used to allow each character to be examined allowing composed and combining characters to be identified together with code points unassigned in Unicode 4.0.¶

This approach would allow negative name caching to be disallowed for strings containing those characters while allowing it for other strings that do not. A larger limit (and a corresponding mask) would make sense for clients used to access many file names containing characters from non-Latin alphabets.¶

A3:

A client might implement its own internationalized file name handling paralleling that of the server. Because the Unicode version used by the server filesystem is unknown, strings for which it is possible that the canonically equivalent string might be different depending on the version of Unicode implemented by the server will have to be identified and excluded from using negative name caching. This would require that strings containing code points unassigned in Unicode version 4.0, and those denoting combining characters that could be parts of precomposed character added to later versions of Unicode be excluded from negative name caching. The necessary filtering could apply to all potential code points although clients might choose to simplify implementation by excluding strings containing code points beyond a certain point, e.g. (U+0FFFF).¶

When a client implements internationalized name handling, it needs to be able to detect when the apparent absence of a file within a directory is contradicted by the occurrence of a file with a distinct, but canonically equivalent, name. In order to efficiently find such names, when they exist, a client typically needs to implement a form of name hashing which always produces the same result for two canonically equivalent names. This can be done by making the contribution of any character to the name hash, equal to the contribution of the corresponding canonical decomposition string.¶

In the case of case-insensitive file systems, the uncertainty to be dealt with includes the version of Unicode implemented by the server as well as the details of the possible case-handling implemented by the server. In addition to the fact that different Unicode versions may have different canonical equivalence relationships, the server may implement different approaches to the handling of issues related to the handling of dotted and dotless i, in Turkish and Azeri. However, the question of whether the server's handling is case-preserving has no effect on client behavior, as is the question of whether the server implements a particular normalization form or implements form-insensitive file name matching. In light of the uncertainty created by the lack of knowledge of the details of the case-related equivalence relation together with the precise Unicode version used by the server to implement its canonical equivalence relation, the following possibilities, arranged in order of increasing value (and difficulty of implementation) should be considered.¶

B1:

The client can simply decline to implement optimizations based on negative name caching on case-insensitive file systems.¶

While this might have a negative effect on performance where significant benefits from negative name caching might be expected, it might be the best option for clients not heavily used to access case-insensitive filesystems.¶

B2:

Filtering similar to that discussed in item A2 could be implemented, although a higher limit is likely to be chosen (e.g. U+07ff) if significant use of non-Latin scripts is expected. Because of the uncertainty regarding the handling of case relationship among characters used for the variant of I used by Turkic languages, this filtering would have to exclude names containing LATIN CAPITAL LETTER I WITH DOT ABOVE and LATIN SMALL LETTER DOTLESS I together with precomposed characters derived from them.¶

In cases in which such filtering did not exclude the item from consideration, it would need to search for files with possibly equivalent names, including those equivalent by canonical equivalence, case-insensitive equivalence, or a combination of the two. This will typically require a form of name hashing which always produces the same hash for equivalent names, similar to that discussed in item A3 but including case-insensitive equivalence as well.¶

B3:

A client might implement its own internationalized, case-insensitive file name handling paralleling that of the server. Because the case mappings are uncertain and the Unicode version used by the server filesystem is unknown, strings for which it is possible that the equivalent string might be different depending on the version of Unicode implemented by the server or the choice of case mappings would have to be identified and excluded from using negative name caching. This would require that strings containing code points unassigned in Unicode version 4.0, and those denoting combining characters that could be parts of precomposed characters added to later versions of Unicode be excluded from negative name caching. The necessary filtering could apply to all potential code points although clients might choose to simplify implementation by excluding strings containing code points beyond a certain point (e.g. U+00FFFF).¶

When a client implements internationalized name handling, it needs to be able to detect when the apparent absence of a file within a directory is contradicted by the occurrence of a file with a distinct, but canonically equivalent name. In order to efficiently find such names, when they exist, a client typically needs to implements a form of name hashing which always produces the same result for two canonically equivalent names. This can be done by making the contribution of any character to the name hash, equal to contribution of the correspond canonical decomposition string.¶

11.3. Client Processing of File Names for Future NFSv4 Protocols

Because of NFSv4 has an extension framework allowing the addition of new attributes in later minor version or in extensions to extensible minor versions. Such new attributes are likely to be optional. They could include a number of useful per-fs attributes to deal with the information gaps discussed in Section 11.2:¶

• The Unicode version used to define the canonical equivalence relation implemented by the server could be provided as an fs-scope attribute.¶
• For case-insensitive filesystems, details regarding the actual case mapping used could be provided as an fs-scope attribute. These details would include the case mapping associated with LATIN LETTER I (i.e. whether the C-type or T-type case mappings or both are to be used). Similarly for characters having F-type case mappings, information needs to be provided about whether the F-type, mapping, the S-type mapping, or both, are to be used.¶

There is little prospect of such additional attributes being REQUIRED. Although the term "RECOMMENDED" has been used to describe NFSv4 attributes that are not REQUIRED, any such attributes are best considered OPTIONAL for the server to support with the client required to deal with the case in which the attribute is not supported.¶

When such attributes are defined and implemented, it would be possible for the client and server to implement compatible internationalization-related file name handling. However, as a practical matter, such compatibility would be considerably eased if there existed unencumbered open-source implementations of the algorithm and tables described in Appendix A. This would allow clients, servers, and server-based file systems, to easily adopt compatible approaches to these issues, each calling a common set of primitives, even though each might have a different execution environment and might be processing file names for different purposes.¶

In the case of case-sensitive file system, the case-mapping attribute is not relevant. In dealing with the non-support of the Unicode version attribute, the client is in the same position as that of clients described in Section 11.2. In the case in which the Unicode version is supported, the client would be able to implement the same version of the canonical equivalence relation implemented by the server, thus avoiding the need for the sort of overbroad filtering mentioned in items A2 and A3 within Section 11.2¶

The case of case-insensitive file systems is more complicated, since there are two OPTIONAL attributes to deal with:¶

C1:

When neither of these OPTIONAL attributes is supported, the client is in the same position as that of clients described in Section 11.2 in dealing with a case-insensitive file system.¶

C2:

When the Unicode version is available but the details of case mapping are not, the client handling will be similar to that specified the options B1 through B3 defined in Section 11.2. However, in cases B2 and B3, it will be possible to reduce the scope of the character filtering applied, by enabling names containing characters defined after Unicode version 4.0 to be processed, as long as none of the case mapping options for those characters is at all problematic.¶

C3:

When the details of case mapping are available but Unicode version is not, the client handling will be similar to that specified the options B1 through B3 defined in Section 11.2. However, in cases B2 and B3 However, in cases B2 and B3, it will be possible to reduce the scope of the character filtering by enabling names containing characters of uncertain case mapping to be processed as long as those character were defined in Unicode version 4.0.¶

C4:

When both of these OPTIONAL attributes are supported, the client has the ability, at least theoretically, to reproduce the internationalization-related file name handling implemented by a server for a case-insensitive file system. However, when the client is unable to provide such an implementation, it is free to ignore the attribute and implement one of the options B1 through B3 defined in Section 11.2.¶

12.1. Effect of IDNA Changes

Overall, the effect of the shift to IDNA2008 is to limit the degree of understanding of the IDNA-based restrictions on domain names that were expected of NFSv4 in RFC7530 [3]. Despite this specification, the degree to which implementations actually implemented such restrictions is open to question and will be discussed in detail in Section 12.2¶

In analyzing how various cases are to be dealt with according to RFC7530, there a number of troubling uncertainties that arise in trying to interpret the existing specification:¶

• There are a number of cases in which "SHOULD" is used that are confusing. According to RFC2119 [1], "SHOULD" means that "there may exist valid reasons in particular circumstances to ignore a particular item, but the full implications must be understood and carefully weighed before choosing a different course". To fully understand a particular "SHOULD", there needs to be enough context to determine whether particular reasons for ignoring the item are in fact valid, and sufficient guidance to understand the implication of ignoring the item. In the absence of such information, the relevant fact is that the peer needs to deal with the item being ignored, making the implications of a "SHOULD" hard to distinguish from those of "MAY".¶
• While the document states. "the general rules for handling all of these domain-related strings are similar and independent of the role of the sender or receiver as client or server", all of the following text is explicitly about the server's options, choices and responsibilities, leaving the client case unclear.¶
• In a number of places within the paragraph describing server approach #1, the word "can" is used as in the text "the server can use the ToUnicode function", leaving it unclear whether the server can choose to do anything else and if so what.¶

The following cases are those where RFC7530 requires use of IDNA handling and this requirement could, if implementations follow them, create potential compatibility issues, which need to be understood.¶

• The degree to which RFC3490 [19] requires that characters other than U+002E (full stop) be treated as label separators, including U+3002 (ideographic full stop), U+FF0E (fullwidth full stop), U+FF61 (halfwidth ideographic full stop).¶
• The degree to which RFC3490 [19] that server or client needs to validate a putative A-label or U-label or to rectify it if it is not valid.¶

12.2. Potential Compatibility Issues Related to IDNA Changes

There are a number of factors relating to the handling of domain names within NFSv4 implementations that are important in understanding why any compatibility issues might be less troubling than a comparison of the two IDNA approaches might suggest:¶

• Much of the potentially conflicting IDNA-related behavior required or recommended for the server by RFC7530 [3] might not actually be implemented, limiting the potential harmful effects of ceasing to mandate it.¶
• Even if such behavior were implemented by servers, no compatibility issue would arise unless clients actually relied on the server to implement it. Given that none of this behavior is made required, the chances of that occurring is quite small.¶

• The range of potential values for user and group attributes sent by clients are often quite small with implementations commonly restricting all such values to a single domain string. This is even though RFCs 7530 [3] and 5661 [4] are written without mention of such restrictions.¶

  Specification of users and groups in the "id@domain" format within NFSv4 was adopted to enable expansion of the spaces of users and groups beyond the 32-bit id spaces mandated in NFSv3 [16] and NFsv2 [15]. While one obstacle to expansion was eliminated, most implementations were unable to actually effect that expansion, principally because the physical file systems used assume that user and group identifiers fit in 32 bits each and the vnode interfaces used by server implementations make similar assumptions.¶

  Given these restrictions, the typical implementation pattern is for servers to accept only a single domain, specified as part of the server configuration, together with information necessary to effect the appropriate name-to-id mappings.¶

• The other uses of domain names in NFSv4, to represent hostnames in location attributes, the values are generated by the server and will normally include only include hostnames within DNS-registered domains.¶

Keeping the above in mind, we can see that interoperability issues, while they might exist are unlikely to raise major challenges as looking to the following specific cases shows¶

• When an internationalized domain name is used as part of a user or group, it would need to be configured as such, with the domain string known to both client and server.¶

  While it is theoretically possible that a client might work with an invalid domain string and rely on the server to correct it to an IDNA-acceptable one, such a scenario has to be considered extremely unlikely, since it would depend on multiple servers implementing the same correction, especially since there is no evidence of such corrections ever having been implemented by NFSv4 servers.¶

• When an internationalized domain in a location string is meant to specify a registered domain, similar considerations apply.¶

  While it is theoretically possible that a client might work with an invalid domain string and rely on the server to correct it to the appropriate registered one, such a scenario has to be considered extremely unlikely, since it would depend on multiple servers implementing the same correction, especially since there is no evidence of such corrections ever having been implemented by NFSv4 servers.¶

• When an internationalized domain in a location string is meant to specify a non-registered domain, any such server-applied corrections would be useless.¶

  In this situation, any potential interoperability issue would arise from rejecting the name, which has to be considered as what should have been done in the first place.¶

A.1. Name Hashes

We discussed in Section 10.1 the construction of a case-insensitive file name hash. While such a hash could also be form-insensitive if the hash contribution of every pre-composed character matched the combined contribution of the characters that it decomposes into.¶

However, there is no obvious way that sort of hash could respect the canonical equivalence of multiple combining characters modifying the same base character, when those combining characters appear in different orders. Addressing that issue would require a significantly different sort of hash, in which combining characters are treated differently from others, so that the re-ordering of a string of combining characters applying to the same base character will not affect the hash.¶

In the hash discussed in Section 10.1, there is no guarantee that the hash for multiple combining characters presented in different orders will be the same. This is because typically such hashes implement some transformation on the existing hash, together with adding the new character to the hash being accumulated. Such methods of hash construction will arrive at different values if the ordering of combining characters changes.¶

In order to create a hash with the necessary characteristics, one can construct a separate sub-hash for composite character, consisting of one non-combining character (may be pre-composed) together with the set (possibly null) of combining characters immediately following it. Each such composed character, whether precomposed or not, will have its own sub-hash, which will be the same regardless of the order of the combining characters.¶

If the hash is to include case-insensitivity, special handling is needed to deal with issues arising from the handling of COMBINING GREEK YPOGEGRAMMENI (U+0345). That combining character, as discussed in item EX6 of Section 10.2 is uppercased to the non-combining character GREEK CAPITAL LETTER IOTA (U+0399) which is in turn lowercased to the non-combining character GREEK SMALL LETTER IOTA (U+03B9). As a result, when computing a case-insensitive hash, when a base character is IOTA (of either case) and the previous base character is ALPHA, ETA, or OMEGA (of the same case as the IOTA), that IOTA is treated, for the purpose of defining the composite characters for which to generate sub-hashes as if it were a combining character. As a result, in this case a string of containing two composite characters will be treated as were a single composite character since the iota will be treated as if it were a combining character. This string will have its own sub-hash, which will be the same regardless of the order of combining characters.¶

The same outline will be followed for generating hashes which are to be form-insensitive (only) and for those which are to be both form-insensitive and case-insensitive. The initial value, representing the base character, will differ based on the type of hash.¶

• In the case-sensitive case, the initial value of the sub-hash will reflect the value of the base character with the only possible need to map to a different value deriving from the existence of OHM SIGN (U+2126), ANGSTROM SIGN (U+212B), and MICRO SIGN (U+00B5) as characters distinct from the letters that represent these code points. This could be done with a mapping table but most implementations would probably choose to implement special-purpose code to do this.¶
• In the case-insensitive case, the initial value of the sub-hash will reflect the case-based equivalence class to which the character (the lower-case equivalent is generally suitable). In this context a table-based mapping is required and this mapping can shift OHM SIGN, ANGSTROM SIGN, and MICRO SIGN to the case-based equivalence class for the corresponding character.¶

Regardless of the type of hash to be produced, values based on the following combining characters need to reflected in the sub-hash. In order to make the sub-hash invariant to changes in the order of combining characters, values based on the particular combining character are combined with the hash being computed using a commutative associative operation, such as addition.¶

To reduce false-positives it is desirable to make the hash relatively wide (i.e. 32-64 bits) with the value based on base character in the upper portion of the word with the values for the combining characters appearing in a wide range of bit positions in the rest of the word to limit the degree that multiple distinct sets of combining characters have value that are the same. Although the details will be affected by processor cache structure and the distribution of names processed, a table of values will be used but typical implementations will be different in the two cases we are dealing as described in Appendix A.2.¶

As each sub-hash is computed, it is combined into a name-wide hash. There is no need for this computation to be order-independent and it will probably include a circular shift of the hash computed so far to be added to the contribution of the sub-hash for the new base or composed character.¶

As described in Appendix A.3 the appropriate full name hash will have the major role in excluding potential matches efficiently. However, in some small number of cases, there will be a hash match in which the names to be compared are not equivalent, requiring more involved processing. It is assumed below that a given name will be searching for potential cached matches within the directory so that for that name, on will be able retain information used to construct the full name hash (e.g. individual sub-hashes plus the bounds of each composite character. These will be compared against cached entries where only the full (e.g. 64-bit) name hash and the name itself will be available for comparison.¶

A.2. Character Tables

The per-character tables used in these algorithms have a number of type of entries for different types of characters. In some cases, information for a given character type will be essentially the same whether the comparison is to be form-insensitive or case- insensitive. In others, there will be differences. Also, there may be entry types that only exist for particular types of comparisons. In any case, some bits within the table entry will be devoted to representing the type of character and entry:¶

• For combining characters, the entry will provide information about the character's contribution to the composite character sub-hash in which it appears.¶
• For case-insensitive comparisons, there need to be special entries for characters, which, while not themselves combining characters, are the case-insensitive equivalents of combining characters. An example of this situation is provided in item EX6 within Section 10.2¶
• For pre-composed characters, the entry needs to provide the initial hash value which is to be the basis for the sub-hash for the name substring including contributions for the base character together with contribution of included combining characters. In addition, such entries will provide, separately, information about the character's canonical decomposition.¶
• For case-insensitive comparisons, there needs to be, for base characters, entries assigning each base character to the case-based equivalence class to which it belongs, although such entries can be avoided if the equivalence class matches the character (usually caseless and lowercase characters.¶
• Also, for case-insensitive comparisons, there will need to be special entries for characters which multi-character string as case-insensitive equivalent of the base character. Examples of this situation are provided in items EX4 and EX5 within Section 10.2. Such entries will need to have a hash-contribution that reflects the hash that would be computed for the multi-character string.¶
• For form-insensitive comparisons, there will be special entries to provide special handling for those cases in which there are two canonically equivalent single characters. Such entries do not exist for case-insensitive comparison since this situation can be handled by a non-standard use of case mapping for base characters by placing these two characters in the same case-based equivalence¶

In the common case in which a two-stage mapping will be used, there will be common groups of characters in which no table entry will be required, allowing a default entry type to be used for some character groups with entry contents easily calculable from the code point.¶

• In the case form-insensitive comparison, this consists of all base characters, with the hash contribution of the character derivable by a pre-specified transformation of the code point value.¶
• In the case case-insensitive comparison, this consists of all base character which are either caseless or equivalence class is the same as the code point, typically lowercase characters. As in the form-insensitive case, the hash contribution of the character is derivable by a pre-specified transformation of the code point value, which matches, in this case, the id assigned to the case-based equivalence class.¶

A.3. Outline of comparison

We are assuming that comparisons will be based on the hash values computed as described in Appendix A.1, whether the comparison is to be form-insensitive or both case-insensitive and form-insensitive.¶

To facilitate this comparison, the name hash will be stored with the names to be compared. As a result, when there is a need to investigate a new name and whether there are existing matches, it will be possible to search for matches with existing names cached for that directory, using a hash for the new name which is computed and compared to all the existing names, with the result that the detailed comparisons described in Appendices A.4 and A.5 have to be done relatively rarely, since non-matching names together with matching hashes are likely to be atypical.¶

Given the above, it is a reasonable assumption, which we will take note of in the sections below, that for one of the names to be compared, we will have access to data generated in the process of computing the name hash while for the other names, such data would have to be generated anew, when necessary. When that data includes, as we expect it will, the offset and length of the string regions covered by each sub-hash, direct byte-by-byte comparisons between corresponding regions of the two strings can exclude the possibility of difference without invoking any detailed logic to deal with the possibility of canonical equivalence or case-based equivalence in the absence of identical name segment.¶

In the case in which the byte-by-byte comparisons fail, further analysis is necessary:¶

• First, the associated base characters are compared, as is discussed in Appendix A.4. When doing form-insensitive comparison this is straightforward. However, when case-insensitive comparison is to be done, there is the possibility that the sub-hash boundaries of the two comparands are different, requiring that a common point in both comparands be found to resume comparison after a successful match. For either form of comparison, if a mismatch is found at this point then the comparison fails, while, if there is match, there must be a comparison of any following combining characters, as described below, before moving on to the region covered by the appropriate sub-string covered by the appropriate next sub-hash for each comparand.¶
• If there is no mismatch as to the base characters, the set of associated combining characters (might be null) must be compared, as is discussed in Appendix A.5. If a mismatch is found at this point then the comparison fails. This may be because the sets of combining characters are different, because there are multiple copies of the same combining character in one of the string, or because the difference in combining character is not one that maintains canonical equivalence (due to combining classes).¶
• When both comparisons show a match, the comparison resumes at the next substring, using a byte-by-byte comparison initially. If the comparison cannot be resumed because one of the strings is exhausted, the comparison terminate, succeeding only if both strings are exhausted while failing if only one of the strings is exhausted.¶

A.4. Comparing Base Characters

In general, the task of comparing based characters is simple, using a table lookup using the numeric value of the initial character in the substring. When doing form-insensitive comparison this is the base character associated with the initial (possibly pre-composed) character, while for case-insensitive comparison it is the case-based equivalence class associated with that character.¶

When doing case-insensitive comparison, issues may arise that result when there is a multi-character string that as the case- insensitive equivalent of a single base character, as discussed in items EX4 and EX5 within Section 10.2. These are best dealt with using the approach outlined in Section 10.1. When it is noted that the current base character (for either comparand) is a character whose associated equivalence class contains one or more multi-character strings, then these comparisons, normally requiring that each base character be mapped to the same case-based equivalence class by modified to allow equivalences allowed by these multi-character sequences.¶

In such cases, there may need to be comparisons involving the multi-character string, in addition to the normal comparisons using the base characters' equivalence class. As an illustration, we will consider possible comparison results that involve characters string within the equivalence class mentioned in item EX4 within Section 10.2¶

• When the base character for both comparands are either LATIN SMALL LETTER SHARP S (U+00DF) or LATIN CAPITAL LETTER SHARP S (U+1E9E), then a match is recognized.¶
• When the base character for one comparand is either LATIN SMALL LETTER SHARP S (U+00DF) or LATIN CAPITAL LETTER SHARP S (U+1E9E), while the other is not, each character in the that other comparand is case-insensitively compared to the corresponding character of the string "ss" with a match being signaled when all such subsequent characters match, except for possibly being of a different case. Because that comparison will involve multiple base characters, the overall comparison point for that comparand will have to be adjusted to reflect character already processed as part of the comparison.¶
• When the base character for neither comparands is either LATIN SMALL LETTER SHARP S (U+00DF) or LATIN CAPITAL LETTER SHARP S (U+1E9E), then matching proceeds normally. As a result, the only cases in which character strings within the equivalence class being discussed will result is where both comparands have one of the strings "ss", "sS", "Ss", or "SS" at the current comparison point.¶

A.5. Comparing Combining Characters

In order to effect the necessary comparison, one needs to assemble, for each comparand, the set of combining characters within the current substring. The means used might be different for different comparands since there might be useful information retained from the generation of the associated string hash for one of the comparands. In any case, there are two potential sources for these characters:¶

• Those deriving from the canonical decomposition of a pre-composed character, treated as a null set of if the base character is not a precomposed one.¶
• Those combining characters that immediate following the base character, which will be a null set if the immediately following character is not a combining character. Note that it is possible, when doing case-insensitive comparison to treat certain character, not normally combining characters, as if they are. Such situations can arise, when, as described in item EX6 within Section 10.2, such non-combining character are the uppercase or lowercase equivalents of combining characters.¶

Although, the two sets of character can be checked to see if they are identical, this is a sufficient but not a necessary condition for equivalence since some permutations of a set of combining characters are considered canonically equivalent. To summarize the appropriate equivalence rules:¶

• Combining characters of different combining classes may be freely reordered.¶
• If combining characters of the same combining class are reordered, then result is not canonically equivalent¶

The rules above do not directly apply to the case, discussed above, in which some non-combining characters are the case-based equivalents of combining characters such as COMBINING GREEK YPOGEGRAMMENI (U+0345). Nevertheless, because of this equivalence, those implementing case-insensitive comparisons do have to deal with this potential equivalence when considering whether two strings containing combining characters or their case-based equivalents match. As a result when comparing strings of combining characters, we need to implement the following modified rules.¶

• When one comparand has a true combining character and the other comparand has an identical one, they may differ in location as long as there is no permutation of combining characters of the same combining class.¶
• When one comparand has a true combining character and the other has a case-insensitive equivalent which is not a combining character, that character must appear last in its string while the combining may character appear in its string in any position except the last. In this case, there are no restrictions based on combining classes.¶
• When both comparands contain a non-combining character case-insensitively equivalent to a combining character, these character must appear last in their respective strings.¶

Although it is possible to divide combining characters based on their combining classes, sort each of the list and compare, that approach will not be discussed here. Even though the use of sorts might allow use of an overall N log N algorithm, the number of combining characters is likely to be too low for this to be a practical benefit. Instead, we present below an order N-squared algorithm based on searches.¶

In this algorithm, one string, chosen arbitrarily id designated the "source string" and successive character from it, are searched for in the other, designated the "target string". Associated with the target string is a mask to allow characters search for a found to be marked so that they will not be found a second time. In the treatment below, when a character is "searched for" only characters not yet in the mask are examined and the character sought has its associated mask bit set when it is found.¶

Each character in the source string is processed in turn with the actual processing depending on particular character being processed, with the following three possibilities to be dealt with.¶

1. For the typical case (i.e. a combining character with no case- insensitive equivalents), the character is searched for in the target string with the compare failing if it is not found.¶

   If it is found, then the region of the target string between the point corresponding to the current position in the source string and the character found is examined to check for characters of the same combining class. If any are found, the overall comparison fails.¶

2. For the case of a combining character with a case- insensitive equivalents, the character is searched for as described in the first paragraph of item 1. However, the compare does not fail if it is not found. Instead, a case-insensitive equivalent character is searched for at the final position of the string and the compare fails if that is not found.¶
3. For the case of a non-combining character that has a combining character as a case-insensitive equivalents, the overall comparison fail if the character is not in the final position within the source string or has already been successfully searched for. Otherwise, the corresponding combining character is searched for in the target as described in in the first paragraph of item 1. The overall compare fails if it is not found.¶

Once all characters in the source string has been processed, the mask associated is examined to see if there are combining character that were not found in the matching process described above. Normally, if there are such characters, the overall comparison fails. However, if the last character of the target was not matched and if it is a non-combining character that is case-insensitively equivalent to a combining character, then comparison succeeds and the remaining character needs to be matched with the next substring in the source.¶