Origin Annotation Format, Version 1

This page specifies the $originSpec header, the file table and the grammar of an annotation. It specifies the sequence when an element has more than one origin. It also specifies the line anchor scheme a1, which is the fingerprint inside an annotation.

Interpret the keywords MUST, MUST NOT, REQUIRED, SHOULD, SHOULD NOT, RECOMMENDED, NOT RECOMMENDED, MAY and OPTIONAL as RFC 2119 describes them.

Header

A file MUST have one $originSpec object at the top level as soon as one _origin annotation is in it, also when the producer wrote no origin of its own and only kept the annotation of an input file. An annotation without a table is unusable, because nothing gives the meaning of its file ids.

The file SHOULD write this object first, so a consumer reads it before the first annotation that needs it.

{
    $originSpec: {
        v: 1,
        files: {
            A: { relPath: "Simple/A.cfg.json5" },
            AllDef: { relPath: "definitions/AllDef.def.json5" },
            registers_yml: { relPath: "vendor/registers.yml" },
        },
    },
    allDef: {
        // ... the configuration data
    },
}

The top level of an export file has one key for each definition. $originSpec is a sibling of those keys. In an input file, the header is at the top level next to $definition.

Field Required Content

v

yes

The version of the format. The value is the number 1.

files

yes

One file entry for each file id. The table is in sequence of the file id.

The header MUST NOT have other fields. Version 1 fixes each other parameter of the format:

  • A column counts UTF-8 bytes. The first column is column 1.

  • The first line is line 1.

  • The normal form and the digest are those of the line anchor scheme a1.

The header has no field with only one permitted value, because a consumer would read that field instead of the version number. A consumer MUST use only v to select its behavior.

Version Numbers

A consumer that finds a value of v that it does not know MUST stop. It MUST NOT use the rules of a version that is near to that value.

v MUST be a JSON number with an integer value. A consumer MUST treat these four headers in the same way as a version that it does not know: no v, a v of a different type, no files, and a files table that holds one file id two times. One behavior then covers each header that a consumer cannot read.

Confµgami reports an error for such a header and does not interpret the _origin annotations of that file.

File Ids & Entries

The files table gives one file entry for each file id. A file entry is an object and never a string.

The table MUST hold one entry for each file that an _origin annotation of this file names, and MAY hold further files, which a consumer MUST accept. A file id depends on the complete set of files of the table.

Otherwise an edit that leaves a file without an annotation drops it and changes the id of each file that shares its prefix.

Property Required Content

relPath

one of the two

The path of the file, relative to the folder of the file that holds this header. For a producer that writes to a stream, relative to the current folder of the producer.

absPath

one of the two

The absolute path of the file. A last resort only.

A file entry MUST have exactly one of the two path properties. An entry with both of them, and an entry with neither of them, name no file, so a consumer MUST treat such a table like the four headers above that it cannot read: it reports the header and does not interpret the _origin annotations of that file.

A file entry MAY have other properties, and a consumer MUST ignore a property that it does not know. A new property does not change v: a producer MAY write one under v: 1, and a consumer of version 1 reads the entry as before.

This is the whole purpose of the object shape. A later version can add a property, for example a hash of the file content, without a change to the shape of the table or to the annotations. A property that needed a new value of v would reach no consumer, because a consumer of version 1 MUST stop at a version that it does not know.

The top level of the header is different: it MUST NOT have other fields. A field there changes the meaning of the complete file, and v MUST therefore control it.

relPath

The path is relative to the folder of the file that holds this header: the folder of the export file, or the folder of the input file. It uses a forward slash as the separator and MUST NOT be absolute. It MAY start with ../, because a source file can be outside that folder. It MUST be in its shortest form: no ./ at the start, no . segment, no .. segment after a segment that is a name, and no slash at the end. A .. segment therefore occurs only in the run of .. segments at the start of the value.

The shortest form is REQUIRED because the digest in a file id is of the path value. Two spellings of one path would otherwise give two file ids for one file, and one object could then hold an entry under each of them.

The base is the file itself and never a workspace root, so a consumer that has the file has the base and needs nothing else. That is what makes the table resolvable for a consumer that cannot run the producer, and it lets a tool that is not Confµgami write a header without knowing anything about a Confµgami workspace.

A producer that writes to a stream and not to a file has no such folder, and the base is then its current folder. The consumer of such a stream cannot resolve the table from its content alone, because the current folder is not in the content.

A file that a producer copies into an export gets a new base.

$originSpec: {
    v: 1,
    files: {
        R: {
            relPath: "registers.csv"
        },
        legacy: {
            relPath: "legacy_registers.csv"
        },
    },
},
absPath

The absolute path of the file, with a forward slash as the separator. A producer MUST use relPath when a relative path can express the location of the file, and MAY use absPath only when none can.

There is one such case in practice. On Windows a source file and the file with the header can be on different drives, and no relative path exists between two drives. A UNC path and a local path are the same case.

An absPath value breaks the first design goal of this format, because the value is specific to one machine and is wrong on each other machine. A producer SHOULD therefore report a warning when it writes one, and a consumer SHOULD show such an entry in a different way, because the entry does not travel.

The characters of a path

A path value holds the characters that the file system of the producer gives. A producer MUST NOT convert the value to normal form NFC.

On some systems a path is a sequence of octets and not a sequence of characters, and a conversion to NFC then gives the name of a file that does not exist. One system stores a name in NFD, a different system stores the octets that a person entered.

NFC has two uses in this specification, and neither changes a stored value: a consumer applies it to both paths of a comparison, and a producer applies it inside the derivation of a file id.

A comparison applies NFC and nothing else. It MUST NOT apply a case folding, because a file system can be case-sensitive and two spellings that differ in case are then two files. On a file system that is not case-sensitive, one file can therefore reach the table under two spellings and two file ids. A producer SHOULD give one file one spelling. Confµgami does this because each path comes from one normalized document reference.

File ids

Confµgami makes a file id from the path. A file id MUST NOT be an index number, because an index table changes each number when a file comes or goes. A file id MUST match [A-Za-z0-9_]+, which keeps it free of each character that the grammar uses as a separator.

An id has a prefix from the file name, and then a digest of the path when the prefix is not unique. The prefix keeps the id readable, and the digest makes it unique.

The input of the derivation is the complete set of files of the table, because a prefix is unique or not unique only inside that set. The result MUST depend on that set only, and never on the sequence in which the producer found the files.

To make the file ids, do these steps:

  1. Take the file name of each file and remove its Confµgami suffix. A suffix that gives the role of the file leaves that role in the prefix:

    • .cfg.json5, .cfg.json, .def.json5 and .def.json give the file name without the suffix.

    • .default.def.json5 and .default.def.json give the file name without the suffix, and then _default.

    • .preconfig.def.json5 and .preconfig.def.json give the file name without the suffix, and then _preconfig.

    • Each other suffix gives the complete file name, with its extension.

  2. Apply NFC, then replace each character that is not in [A-Za-z0-9_] with an underscore. The result is the prefix. Use one underscore as the prefix if step 1 gave an empty name, which happens for a file whose complete name is a suffix, for example a file named .cfg.json5. A file id MUST NOT be empty.

  3. A file whose prefix belongs to no other file of the table has that prefix as its id.

  4. Each file that shares its prefix with another file of the table has the id <prefix>_<digest>. The digest is PATHDIGEST of the path value of its own file entry.

  5. If two ids of the table are still equal, put an underscore and a decimal number from 1 after each of them. Sort those files by their path value to give the numbers. Repeat this step until each id of the table occurs one time only, because the result of the step can be equal to the id of a further file again.

PATHDIGEST(p) is FINGERPRINT of the normal form NFC of p, and then a replacement of each hyphen of that result with an underscore. It is 6 characters from [A-Za-z0-9_], so a file id keeps its shape. The digest of a path and the digest of a line are therefore the same function with the same alphabet.

The replacement is necessary because base64url holds the hyphen and the grammar uses the hyphen as a separator. It maps two characters of the alphabet onto one, so two different paths can give the same 6 characters, and step 5 covers that case in the same way as an equal digest.

Simple/A.cfg.json5                  -> A
definitions/Dp.def.json5            -> Dp
definitions/Dp.default.def.json5    -> Dp_default
definitions/Dp.preconfig.def.json5  -> Dp_preconfig
vendor/registers.yml                -> registers_yml

two files with the same name
  Simple/A.cfg.json5                -> A_7Lm2Qx
  Other/A.cfg.json5                 -> A_Kd4nZs

Step 1 keeps the role in the prefix for a reason. Dp.def.json5, Dp.default.def.json5 and Dp.preconfig.def.json5 are the normal layout of a definition with layered values, and all three are sources of a merge. Without the role their three prefixes are equal, and all three files would carry a digest although their names are different.

Step 4 uses the path of the file itself and nothing else, so the derivation needs no repetition and no comparison with the ids of a different group. It changes each member of a group and not only the member that came later, so a new file that collides with a file in the table also changes the id of that file, and each annotation that uses that id. That is the cost of a readable id in the usual case. The other rule, to change only the file that came later, makes each id depend on the sequence in which the producer found the files, and that sequence is not part of the input. A new file that collides with nothing changes no id.

Step 5 exists for completeness only. It needs two files with an equal prefix and an equal digest, or a file whose name is already the qualified id of a different file. Each round of the step makes the ids of a group longer, so the repetition stops.

The digest is of the path value of the entry and not of the content of the file, so the id does not change when a person edits the file. It does change when the export goes to a different folder, but each relPath of the table changes in that case anyway.

The author of an input file selects the ids in its header, and those ids are valid only inside that file. The export makes each output id again from the path, so the ids of an author never come into the export file. Two input files MAY also use one id for two different paths.

Uncovered Entry

A consumer can find an entry with a file id that the files table does not hold, from an error of the producer or from an edit of a person.

The consumer MUST report such an entry as not valid. It MUST NOT use the entry, and it MUST NOT take a file id that is near to it. It MUST keep each other entry of that object, because each entry stands alone.

A file with an _origin annotation and no $originSpec object has no table at all. Each of its entries is then not valid, by the same rule. Confµgami reports a warning for such an input file and does not interpret its annotations. It keeps the annotations in the output, because an annotation is data of the author and not a result of the trace.

Annotation Grammar

The _origin annotation holds the origin. One entry has this form:

single   := fid ':' lineRef ':' col [ '~' ctx '.' own ]
lineRef  := line | '+' zDelta | '-' delta
fid      := [A-Za-z0-9_]+
line     := [1-9][0-9]*            absolute number of the start line
delta    := [1-9][0-9]*            delta from the reference to the start line
zDelta   := 0 | [1-9][0-9]*        the same, and a delta of zero
col      := [1-9][0-9]*            first column of the element
ctx, own := 6 characters from [A-Za-z0-9_-]
A:11:9~kQ3fAb.7Lm2Qx              line 11, column 9
A:+2:5~Rj8pQm.Vc4nZz              2 lines after the reference, column 5
registers_yml:-3:9                3 lines before the reference, a transitive origin without an anchor

An entry has three fields with a colon between them, and the sign is part of the second field: no sign gives an absolute line number, a plus sign or a minus sign gives a delta. A tilde after col gives the anchor, and the end of the entry gives none.

A file id cannot contain a colon, a plus sign, a minus sign, a tilde or a dot. A parser can therefore read an entry from left to right, with no look-ahead.

An Entry Names a Position and Not a Range

An entry gives the start of the element and never its end.

A consumer MUST use the position as the start only, and MUST NOT assume that the element stops at the end of the line or at any other place. A consumer that needs the end of a traced element has the source file open at that point and can read the end from it.

An end in the entry would break the second design goal of the format, which is the reason there is none. The end line of an object is the end line of its last child, so a new property of a leaf element changes the recorded end of each object above it, in each file of the chain, and the root object of a file then changes for each edit anywhere in that file. Those objects did not move: their start, their identity and their anchor are unchanged.

The end is also the one part of an entry that a consumer can never check. The anchor covers the start line, so a consumer that found a line again has no way to find out that the end is no longer correct.

The author of a transitive entry has the same rule and usually has a position anyway: a row of a register list, a cell of a spreadsheet, a message of a code generator.

Canonical Form of a Number

A number in an entry MUST NOT have a leading zero. A delta of zero MUST be written as +0, and the form -0 is not valid. Both rules exist because the format requires the same output, byte for byte, for the same input, and a number with two valid spellings would break that.

Each number MUST be at most 2147483647, and a consumer MUST report an entry with a larger number as not valid. A larger value names no line of a real file, and the limit lets a consumer keep a line number and a column number in a signed 32-bit integer. A consumer MUST still resolve a delta in a type of at least 64 bits, because the sum of a reference and a delta can leave that range and an overflow gives a position instead of a message.

Each entry has its file id, so the annotations are independent of the sequence in the export file, and there is no register for a current file.

Line Numbers and Column Numbers

The column number is absolute, and the format MUST NOT write it as a delta. A column number changes only when a person edits its own line, and such an edit is already a small change.

  • col is the first column of the element.

  • A column number counts the UTF-8 bytes of the text before it on that line. The first column is column 1. A tab is one column.

  • A column number for the display of the text is different. It depends on the settings of the editor. The format MUST NOT store it.

  • A column number MUST be at the start of a UTF-8 character. A value inside a character of more than one byte is a defect in the generator.

A column number has no anchor. Step 3 and step 4 of the normal form remove the whitespace at the start of a line, so an anchor stays correct after a change to the indentation of the complete file, while each column number of that file is then wrong and nothing in the entry shows it. A consumer that found a line again SHOULD therefore use the line as the target of a jump, and SHOULD use the column numbers as an indication only.

Numbering of the Producer

The line numbers and the column numbers of an entry MUST be the numbers of the rules for reading the file. The anchor uses those rules, so a producer with a different numbering describes one line and names a different one.

A producer usually takes its positions from a parser, and a parser does not always follow the same rules. The terminators of this specification are those of a JSON5 parser, which is why the list of terminators is short, and the line numbers therefore agree without further work.

One difference is known, and it is a column number. The rules remove a BOM before the first line, so a parser that keeps the BOM gives a column number on line 1 that is 3 higher. A producer with such a parser MUST correct the values before it writes them, and a test of the conformance SHOULD use a file with a BOM.

How to Resolve Deltas

A delta is relative to the start line of the nearest parent object with an origin for the same file id. That parent object is the reference of the delta, and the delta is never relative to the delta value that the reference contains. If no parent object has an origin for that file id, the annotation MUST be absolute.

An array is not an object and holds no annotation, so the parent object of an element of an array is the nearest object above that array. The reference is always unique, because an object MUST NOT have two origins with the same file id.

The root object of the file is a parent object like each other object. An annotation there records the origin of the complete file, which is the usual entry of a generated file, and it is the reference of each delta below it that has no nearer one.

_origin: "R:2:5~aB3dEf.7Lm2Qx", // absolute, no parent object with an origin
limit: {
    _origin: "R:+3:9~kQ3fAb.Vc4nZz", // 2 + 3 = 5, relative to block
    maxCurrent: {
        _origin: "R:+1:13~Rj8pQm.Xw5tHn", // 5 + 1 = 6, relative to limit
        value: 12,
    },
},

The rule is the same for an entity and for a struct, because nothing in the JSON shows which of the two an object is, and a marker for the difference would make the format dependent on that marker.

An entity can move 300 lines down its source file, and only one number in the export file then changes. A different sequence in the export file changes no annotation.

Recorded Line and the Found Line

An entry has two start lines, and a consumer MUST keep the two apart.

Recorded line

The line of the element in the revision of the source file that the producer read. For an absolute entry it is the value in the entry. For a delta entry it is the recorded line of the reference, and then the delta.

Found line

The line of the element in the revision of the source file that the consumer has. The consumer gets it from the search with the anchor, and that search needs a line to start at.

An entry without an anchor has no search, and its found line is its recorded line. A transitive entry is usually such an entry, and an entry below it in the same file then keeps the movement that the entry above it did not find.

A consumer that only reads the export file, and never opens a source file, needs the recorded line only.

A consumer that opens a source file MUST resolve the entries of one file id from the reference down to the entries below it. The start line of the search is:

  • the recorded line, for an entry without a reference, and

  • the found line of the reference, and then the delta, for an entry with a reference.

A consumer MUST NOT start the search of a delta entry at the recorded line of that entry.

A start line of 0 or less, and a start line after the last line of the file, are both possible, because a delta is the difference of two positions that can move against each other. A consumer MUST run the search with such a value and MUST NOT stop with an error. The search tests only the candidates that exist, so a start line outside the file gives a search on one side only, or NotFound.

This rule is the reason for the delta form. Each search then covers the movement of one step only, and not the movement that each step above it collected. An element that keeps its position inside its reference is found again, whatever the distance that the reference moved, as long as the reference itself was found.

The limit of the rule is hard. A step that moved further than the search radius R gives NotFound for that entry, and each entry below it in that file is then also NotFound, because its start line has no value. A consumer SHOULD report the step that failed and SHOULD NOT report each entry below it, because the one failure is the cause of all of them.

An entry that is not valid is a reference without a value in the same way. A consumer MUST treat each entry below such a reference as unresolvable for that file id, and it SHOULD report the entry that is the cause and not the entries below it. It MUST NOT take the next parent object above the entry that is not valid as the reference, because the delta is not the difference to that object.

Line Anchor Scheme a1

An anchor is a small token for one line of a text file. A consumer uses it to find the same line again in a later revision of that file, after a change to the format of the file or after a person added or removed other lines.

An anchor gives a location. It is not a check of the integrity of the data, and it gives no protection against an attack.

Version 1 of the format makes a1 the anchor scheme. A change to the rules in this chapter makes each stored anchor invalid, and MUST therefore also change the version of the format.

Terms

Raw line

A sequence of characters with no line terminator in it. The sequence is as long as possible.

Line terminator

LF (U+000A) or CRLF (U+000D U+000A). The two forms are equivalent. No other character is a line terminator.

A CR (U+000D) that is not followed by LF is not a line terminator. It is whitespace inside a raw line, and step 3 of the normal form makes it a SPACE. U+000B, U+000C, U+0085, U+2028 and U+2029 are the same case.

This list is short on purpose. A JSON5 parser splits its lines at LF, and the format needs the line numbers of the producer and of the anchor to be the same numbers. A terminator that a parser does not know would make the two disagree without a message.

A file that uses a single CR as its terminator is therefore one raw line, and its anchor is the fingerprint of the complete file. The result stays deterministic and gives a correct Strong or NotFound, but it finds no position, because the file has one position. Such files are from a system that is no longer in use.

An editor can show a character of this list as a line break, and the line number of this specification is then not the line number that the editor shows.

Line number

The position of a raw line in the file. The first raw line is line 1. Each line number in this specification is 1-based.

Window

The three line numbers (i - 1, i, i + 1), in that sequence.

How to Read the File

Confµgami reads an anchored file as text and does not parse it. The source file of a transitive origin is not always JSON5 and not always valid UTF-8, so the steps below give a result for each sequence of bytes.

  1. Read the file as a sequence of octets.

  2. If the first three octets are EF BB BF, remove them.

  3. Decode the octets as UTF-8. Replace an invalid sequence with U+FFFD. Use one U+FFFD for each invalid subpart that is as long as possible. An invalid sequence MUST NOT stop the process with an error. This rule makes the result deterministic for a file that is not UTF-8.

  4. Divide the text into raw lines at each line terminator. A line terminator at the end of the file MUST NOT make an empty last line.

  5. A file with no octet, and a file that holds only a BOM, has no line. No anchor exists for such a file, and a search in it gives NotFound.

Normal Form of a Line

To make the normal form of a raw line, do these steps in this sequence:

  1. Remove each character in the set {U+200B, U+200C, U+200D, U+FEFF}.

  2. Apply Unicode Normalization Form C (NFC).

  3. Replace each sequence of whitespace with one SPACE (U+0020). Each sequence must be as long as possible.

  4. Remove a SPACE at the start of the line and a SPACE at the end of the line. A line that is one SPACE becomes empty, because that one character is both.

Step 1 is before step 2, and the sequence of the two is part of the specification. A zero-width character can be between a base character and a combining mark: its removal makes the two adjacent, and NFC then composes them into one character. NFC before the removal does not see that pair, so its result is not in normal form, and the other sequence gives a different digest for a line that must give the same one.

The whitespace set of step 3 is exactly these 29 code points:

Code points Content

U+0009..U+000D

TAB, LF, VT, FF and CR

U+001C..U+001F

the four separators

U+0020

SPACE

U+0085

NEXT LINE

U+00A0

NO-BREAK SPACE

U+1680

OGHAM SPACE MARK

U+2000..U+200A

the spaces of the General Punctuation block

U+2028

LINE SEPARATOR

U+2029

PARAGRAPH SEPARATOR

U+202F

NARROW NO-BREAK SPACE

U+205F

MEDIUM MATHEMATICAL SPACE

U+3000

IDEOGRAPHIC SPACE

This list is complete and normative. An implementation MUST use it and MUST NOT read the set from the Unicode database at run time. A later version of Unicode can add a code point to the White_Space property, and two implementations that read that property would then use a different set and give different digests for one line, without a message.

The list is the White_Space property of Unicode 16 together with U+001C to U+001F, so it is the same set as str.isspace() in Python. char::is_whitespace() in Rust is the list without U+001C to U+001F, so a Rust implementation needs one more test for those four code points.

This is the one rule where two implementations can disagree without a message, and the result looks like a lost line and not like a defect. A test of the conformance MUST therefore include a test for each of the four separators.

Step 3 and step 4 remove the indentation of the line, and that is intentional: the cfu format command changes the indentation of a file, and an anchor that does not survive such a change has no value. The limit of the two steps is that an anchor MUST NOT be used where the whitespace at the start of a line is part of the data.

Window String

The window string for the line number i has three parts. Put an LF between the parts.

Part Content

1

The normal form of line i - 1. If i is 1, use the character U+0002 (BOF).

2

The normal form of line i.

3

The normal form of line i + 1. If i is the last line, use the character U+0003 (EOF).

The BOF text and the EOF text give the difference between the limit of the file and an empty line next to the target line. Without them, both cases give an empty part.

Fingerprint

To calculate FINGERPRINT(s), do these steps:

  1. Encode s as UTF-8.

  2. Calculate FNV-1a-64.

  3. Apply the fmix64 function of MurmurHash3.

  4. Take the 36 most significant bits.

  5. Encode the bits with 6 bits for each character. Start with the most significant group. Use the base64url alphabet of RFC 4648, section 5, without a pad character.

FNV-1a-64
  h = 0xCBF29CE484222325
  for each octet b:  h = (h XOR b) * 0x100000001B3   mod 2^64

fmix64
  h ^= h >> 33
  h  = h * 0xFF51AFD7ED558CCD   mod 2^64
  h ^= h >> 33
  h  = h * 0xC4CEB9FE1A85EC53   mod 2^64
  h ^= h >> 33

The result is 6 ASCII characters from the set [A-Za-z0-9_-].

FNV-1a alone gives a bad distribution for short inputs that are almost equal, and the inputs here are exactly of that type. The fmix64 function is therefore REQUIRED, and after it a simple cut of the bits is correct: an XOR fold is not necessary.

All arithmetic is modulo 264, and an implementation MUST make the operation explicit where a language does not do this by default. In Rust, use wrapping_mul, because the * operator stops the program with overflow-checks. In a language with integers of any size, apply a mask with 0xFFFFFFFFFFFFFFFF.

The digest is not a cryptographic digest, and that is intentional. An attacker could control the content of a file, and a different system could trust the anchor.

Two Parts of an Anchor

An annotation gives a position, and the anchor is for the line of that position.

An anchor has two parts:

Part Type Content

ctx

6 characters

The FINGERPRINT of the window string of the start line.

own

6 characters

The FINGERPRINT of the normal form of the start line.

An annotation MUST hold both parts. A dot separates them and a tilde is in front of them. They are the last part of an entry, and they are OPTIONAL only for a transitive origin.

ctx is exact, but a small change makes it invalid. own accepts more, but it is not always unique. Both parts together give a result of a lower quality instead of no result at all. A digest of one line cannot give the difference between two lines with the text },. A window digest has the other problem: a change to a line next to the target line makes it invalid although the target line itself did not change.

The line number in an annotation is a start point for a search and never an identity. The rule for the recorded line and the found line gives that start point.

Given a decoded revision of the file, an anchor A, a start line L and a search radius R. L comes from the rule for the recorded line and the found line, and it is a start point and never an identity.

for d = 0, 1, ... R:
    for candidate in (L + d, L - d):              # in that order
        skip if candidate < 1 or candidate > line count
        skip the second candidate if d = 0        # both are L
        if FINGERPRINT(window string of candidate) = A.ctx:
            return (candidate, Strong)
        else if no weak candidate recorded
             and FINGERPRINT(normal form of candidate) = A.own:
            record candidate as the weak candidate

if a weak candidate was recorded:
    return (weak candidate, Weak)
return NotFound

A Strong result means that the line and both of its neighbours are unchanged. A Weak result means that the line itself is unchanged but at least one neighbour changed. NotFound means that no candidate within R matched either digest.

The search MUST NOT return a weak candidate before it has tested every candidate within R for a strong match. It records the first weak candidate and continues, so a strong match at the edge of the radius still wins over a weak match at distance 0. Because d increases monotonically, the first strong match is the one nearest to the recorded position, which is the correct tie-break for a file with repeated content.

A consumer SHOULD use a Weak result only as an indication, and SHOULD show it in a different way to the user, because it means that the lines next to the target line changed.

The RECOMMENDED value of R is 200. An implementation SHOULD keep the normal forms of a file in a cache: one search tests up to 2R + 1 candidates, and each strong test makes the normal form of three lines.

R is not in the data. Two consumers with a different R can therefore give a different result for one file and one anchor. A larger R finds a line that moved further, and it also gives a higher rate of a false result. A consumer SHOULD document its value of R. A producer that makes the check at the time of the export SHOULD do the same, because its warnings depend on that value.

Properties and Limits of an Anchor

An anchor stays correct after these changes

  • a different line terminator, LF or CRLF

  • a BOM at the start of the file, or no BOM

  • a line terminator at the end of the file, or none

  • whitespace at the end of a line

  • a different width of the indentation, or tabs in place of spaces

  • a new zero-width character in a line

  • a different Unicode composition, NFC or NFD

  • a new line or a removed line outside the window

An anchor does not stay correct after these changes

  • a change to the visible content of the line itself, because the test is exact and not approximate

  • a change to a line next to the target line, which makes a Strong result into a Weak result

  • a new line at the start of the file, for line 1, and a new line at the end of the file, for the last line

    The BOF text and the EOF text are part 1 and part 3 of the window string of those two lines. A new line at that limit of the file replaces one of the two texts, so the change is inside the window and not outside it. The own part does not change, so the result is Weak and not NotFound.

A line with no content of its own

The normal form of an empty line, and of a line that holds whitespace only, is the empty string. Each such line of a file therefore has one own digest. A Weak result on such a line says only that the found line is also empty, which a consumer sees without an anchor, and it SHOULD therefore show such a result as no result. The start line of a traced entry always holds a key or a value, so this case comes from a transitive entry that carries an anchor.

Collisions

The digest has 36 bits, which are about 6.9 * 1010 values. One search over n candidates tests up to 2n digests, one for ctx and one for own. The rate of a false result for one search is therefore about 2n / 236. An R of 200 gives 401 candidates and a rate of about 1.2 * 10-8, which is one search in 108.

The rate for one search is not the number that a user sees: the number for the user is the rate for a complete export. An export with 105 annotations gives about one false result in 103 exports.

A search over a complete large file gives a much worse rate, because n is then the number of lines of the file. Such a search is NOT RECOMMENDED with a digest of 36 bits.

Conformance Tests of the Anchor

The cases are in four groups. The first tests the normal form and the digest of one line, and each of its cases asserts a digest. The second tests the search, and each of its cases asserts a candidate and a result of Strong, Weak or NotFound. The third and the fourth are for a producer only.

An implementation is conformant if it gives the correct result for each case. The expected values stay with the implementation, so they cannot become different from the code that makes them. The numbers of the cases are labels, and they run without a gap from the first group to the last.

Cases of the Fingerprint

Case Content

1

An ASCII line in a file of one line. This tests both the BOF text and the EOF text.

2

The same content as an LF file and as a CRLF file. The two anchors are equal. A third file with the same content and a single CR as its terminator is one raw line, and its anchor is therefore different.

3

The same content with a BOM and without a BOM.

4

A tab and four spaces as the indentation. The two anchors are equal.

5

A line with U+00A0, U+2009 and U+3000. This tests step 3 of the normal form.

6

A line with U+001C to U+001F. Python and Rust are different here.

7

The character é as U+00E9 and as U+0065 U+0301. This tests NFC.

8

The characters U+200B to U+200D and U+FEFF inside a line.

9

An emoji with a ZWJ. Step 1 removes the ZWJ.

10

An anchor on line 1 of a file, and an anchor on a line that follows an empty line. Both give an empty part 1, but only line 1 uses the BOF text.

11

Octets that are not valid UTF-8. The U+FFFD result is deterministic.

12

A base character, then a zero-width character, then a combining mark. Step 1 removes the zero-width character and step 2 then composes the pair. This tests the sequence of the two steps. The other sequence gives a different digest.

13

A line that is one SPACE, and an empty line. The normal form of both is empty.

Cases of the Search

These two cases need a complete search and not a digest of one line.

Case Content

14

More than one line with the same content. This tests the rule for the nearest strong candidate, and the rule that a strong candidate at the edge of the radius wins over a weak candidate at distance 0.

15

An empty file, and a file that holds only a BOM. Neither has a line, and a search in it gives NotFound.

A Case of a Producer

This case is not a case of the anchor, but a producer that fails it names the wrong column.

Case Content

16

A file with a BOM, which tests the column numbers on line 1.

A Case of the File Ids

PATHDIGEST is normative, and each file id of a group with an equal prefix depends on it.

Case Content

17

A path value whose FINGERPRINT holds a hyphen. This tests the replacement of the hyphen with an underscore. An implementation that keeps the hyphen gives a file id that the grammar cannot hold, and one that applies the replacement to a different string gives a different id for one path.

More Than One Origin

An element after a merge usually has more than one source, and the annotation is then an array. The first entry is the weakest source and the last entry is the strongest source, which is the only sequence that a consumer can understand without this specification. The sequence of the sources is the one rule that builds the array, and a producer MUST NOT move an entry out of it for any other reason.

A definition whose configurationFileMode is not a mergeable mode gives each element one source. Each traced annotation of such a definition is therefore one entry and never an array, and the rules of this chapter are then true without work.

To build the array, take the sources in sequence from the weakest to the strongest. For each source, write these entries:

  1. the position of the source in its own .cfg.json5 file or .def.json5 file, and then

  2. the transitive origins of that source, in the sequence that the source gives.

_origin: [
    "base:7:3~aB3dEf.7Lm2Qx",       // weakest source, a later source replaced it
    "base_regs_csv:12:5",           // its transitive origin, stays with it
    "prod:12:5~kQ3fAb.Vc4nZz",      // the strongest source
    "prod_regs_csv:31:1",           // its transitive origin
],

These rules are part of the specification:

  • An object MUST NOT have two origins with the same file id. Each file id occurs one time only in the array of one object. Two different objects can of course use the same file id. Two sources of one object can name one upstream file, and the rule for two sources with one upstream file then gives the entry that stays.

  • A $fileType priority gives the sequence of the sources, from the weakest to the strongest. See Multi-File Configurations and Merging for that priority.

  • That priority exists only in the merge mode MultipleFilesEntitiesMergeableWithPriority. In each other merge mode no source has a priority, and the sequence of the sources is the sequence of the merge.

  • Each source of that mode has a priority, also a file that gives no $fileType. Such a file has the value UserConfig, which is in the middle of the order and not the weakest of it, so a producer MUST NOT treat a missing $fileType as a missing priority.

  • A default inside a .def.json5 file is not a source. Only a .default.def.json5 file is a source, with the priority DefaultValues, which is the lowest of the order and therefore first in the array.

  • Two sources with the same priority, and two sources without one, keep the sequence of the merge. That sequence MUST be deterministic. Two runs with the same input MUST give the same output, byte for byte.

  • A transitive origin MUST NOT move in front of a stronger source. An entry from a source that a stronger source replaced can therefore never be the last entry.

  • The last entry is the best target for a jump. It is the transitive origin of the strongest source. The last entry is the strongest source itself if that source has no transitive origin, and also if the rule for two sources with one upstream file dropped the entry of that origin.

  • A .default.def.json5 file and a .preconfig.def.json5 file are not transitive. They are normal sources with a $fileType priority. The rules put them in sequence with that priority, the same as each other source.

Two Sources with One Upstream File

Two sources of one object can name one upstream file, and two generated .cfg.json5 files from one register list are the usual case. The export makes a file id from the path, so the two entries get one id, and an object MUST NOT hold one file id two times.

One entry for that file id stays and each other entry for it is dropped:

  1. Group the entries of the object by file id.

  2. A group of one entry keeps that entry at its position.

  3. A group of more than one entry keeps one entry, with two tests in this sequence:

    • First, a traced entry beats a transitive entry. The traced entry is a source of the merge, it names the position of the element itself, and it carries an anchor. A transitive entry is a record of an author about the same file, and it can name a different position in it.

    • Then, between two entries of one kind, the entry of the stronger source wins.

    • Two traced entries of one file id would need two sources in one file, so the case does not occur. A producer that can make it keeps the entry that comes earlier in the array.

  4. The entry that stays keeps the position of its own source in the array.

  5. Each other entry of the group is dropped.

The first test comes first because a weak source can be the upstream file that a strong source declares. The traced entry for that file is then the better entry, although its source is the weaker one.

// base.cfg.json5 and prod.cfg.json5 both come from vendor/regs.csv
_origin: [
    "base:7:3~aB3dEf.7Lm2Qx",       // weakest source
    "prod:12:5~kQ3fAb.Vc4nZz",      // the strongest source
    "regs_csv:31:1",                // the upstream of prod, the upstream of base is dropped
],

A producer MUST make these three steps in this sequence:

  1. Re-derive the file id of each entry from the path. Two entries of two input files can name one file under two ids of their own, so a collision appears only after this step.

  2. Reduce each object, as above.

  3. Choose the line form of each entry, absolute or delta, against the result of step 2.

The sequence of step 2 and step 3 is part of the specification. The reference of a delta is an entry of an ancestor object, and step 2 can drop that entry. A producer that chooses the form first names a reference that the export file does not hold, and a consumer then resolves the delta against a different entry, or against none.

The history is not lost. Each source keeps its own entry, and the _origin of that source names the upstream file of that source. A consumer that wants the upstream of a value that a stronger source replaced opens the weaker source and reads the annotation there, so the chain is one step longer and no link of it is missing.

The other rule, one entry for each source, needs a marker in the format for the source that an entry belongs to. This specification has no such marker: a consumer cannot see from an entry whether it is a source of the merge or an upstream file of one. A marker would be a new part of the grammar for a case that costs one step to follow.

Strongest Source and the Value

For a parameter, the strongest source is the source of the value in the output, so the last entry of the array names the file that a person must open to change that value.

More than one source can have the highest priority. Those sources then hold equal values, because a difference between two sources of the same priority is a conflict and an error. Each of them is therefore the source of the value, and the format names the last of them. A producer MUST NOT use a different rule to select one of them, because the sequence of the sources is the only rule that builds the array.

For a struct, an entity and a union, no source is the source of the value. Each source contributes its own properties and the object holds the sum of them, so the last entry is the strongest source and nothing more. An object of that kind has no effective source, and this specification gives it no name.

A configuration with an unresolved conflict has no value and no strongest source. It is an error, so it never reaches an export and never reaches this format.

The rule for one file id keeps the reference of a delta unique. Two origins with one file id would give two possible references, and the rule for two sources with one upstream file keeps the reference unique in the one case that can break it.

A value can come from two places in one source file. The author then writes the one location that a person must open, because an object holds one entry for one file id.

An array MUST NOT hold a composition. The properties of an object can come from different files, and each property then has its own origin, while the parent object has the origin of its own declaration.

Three Shapes of the Value

_origin has one parameter with the multiplicity 1..*. All three shapes are therefore the same annotation, here on three parameters of one file:

scalarShape: {
    _origin: "R:5:9~kQ3fAb.7Lm2Qx",
    value: 1
},
arrayShape: {
    _origin: [
        "R:4:3~aB3dEf.Vc4nZz",
        "legacy:5:5"
    ],
    value: 2
},
objectShape: {
    _origin: {
        source: [
            "R:4:3~aB3dEf.Vc4nZz"
        ]
    },
    value: 3
},

A generator writes the first shape for one entry and the second for more than one entry. Confµgami MUST accept all three shapes in an input file, and it keeps both the entries of the author and the traced entries.

No Origin

An element without _origin has no origin, and the origin is then not known. A consumer MUST NOT think that the parent object gives its origin to the child.

Transitive Origins

A transitive origin is an _origin entry from the author of a .cfg.json5 file. The entry records that a different source made the file.

  • The header of that input file MUST declare the source file. The export then makes a file entry for it in the output table, with a new id from the path, and MUST NOT copy a property of the input entry that it does not know.

  • An entry of an input file gives the export a position and never a spelling of it. The export gives the path a new base and the delta a new reference.

  • The anchor is OPTIONAL, and usually there is none, because the author must calculate it. It is the only optional part of an entry, because an entry names a position and the author of a transitive entry usually has one anyway.

  • The source file is not always JSON5 and not always UTF-8, so version 1 gives no rule for its column numbers. Its positions are those of the tool that made it, and a consumer MUST use them only as an indication.

The New Base of a Path from an Input File

A relPath of an input file is relative to the folder of that input file, and the export file usually sits in a different folder. The export MUST therefore give the path a new base before it writes it into the output table:

  1. Make the path absolute against the folder of the input file.

  2. Make it relative again against the folder of the export file.

  3. Use absPath if step 2 has no result, and report a warning.

An export that copies the value without this step names a file that does not exist, or a wrong file. An absPath of an input file needs no such step and goes into the output table as it is.

The New Reference of a Delta from an Input File

A delta of an input file is relative to the nearest parent object of that input file with an origin for the same file id. The export has a different tree of objects, so that reference is not the reference of the export:

  • The export puts the sources of a merge into one object, so an object of the export has the entries of more than one input file.

  • An ancestor of the input file can lose its entry for that file id, because the rule for two sources with one upstream file dropped it.

  • An ancestor of the export can hold an entry for that file id that no ancestor of the input file had.

The export MUST therefore calculate the line of each entry again, and MUST NOT copy the lineRef of an input entry:

  1. Resolve the entry against the tree of its own input file, from the reference down, to the absolute recorded line. This uses the header and the objects of that input file only.

  2. Choose the form against the tree of the export, in the same way as for a traced entry. The entry is absolute when no ancestor object of the export holds an entry for that file id, and a delta against the absolute recorded line of the nearest such ancestor otherwise.

A copied lineRef names a wrong line as soon as the two trees are different, and it names it without a message. The absolute recorded line of the entry is the value that both trees share, so the export goes through that value.

The rule for a path and the rule for a delta are the same rule in two places: an entry of an input file gives the export a position, and never a spelling of that position.

The Length of a Chain

This specification gives the length of a chain no limit. A producer MUST NOT remove an entry of an input to make a chain shorter, because each entry names a file that a person can open. A consumer that shows a long chain SHOULD show the first entry and the last entry, and SHOULD let the user open the entries between them.

Check at the Time of the Export

The export opens each upstream file of a transitive entry that it can find, and only such a file. It reads it with the rules for a file that is not UTF-8, so each sequence of bytes is possible, and then finds the position of the anchor again. A source of the merge needs no such check: the producer read that file in this run, so a search would give Strong for each of its traced entries.

If the export cannot find the anchor again, it reports a warning that gives the nearest weak match, if there is one. A source file that is not available is not an error, because it is possibly not part of this checkout.

The check reports and MUST NOT correct.

The export makes this check only at the time of the export. The parser of a .cfg.json5 file MUST NOT read a source file, so the LSP interface is not slower and no source file becomes part of the supervised file set.

How to Write the Output

These rules are as important as the format itself, because a correct format still gives a bad diff if the output is not correct.

  • Write the output with an indentation, in each output format. Put one annotation on each line. A compact output on one line has no diff at all, so it loses the second design goal of this format.

  • Keep the sequence of the keys equal between two runs. A generator MUST NOT use the sequence of a hash map. A sorted sequence of the keys meets this rule, and so does a fixed sequence.

  • This specification gives no position for _origin inside an object. A reader finds the annotation by its key and never by its position. A sorted sequence of the keys puts _origin in front of each property whose name starts with a lower-case letter, which is each property of a configuration.

  • Put the files table in sequence of the file id. Put an array of origins in the sequence of the application, and not in alphabetic sequence.

  • A file id is a key of the files table, and the grammar of a file id permits an id that a JSON5 output cannot write without quotation marks, for example an id that starts with a digit. Such a key MUST get quotation marks. A JSON output quotes each key anyway.

  • Two runs with the same input MUST give the same output, byte for byte. For a producer that writes to a stream, the current folder is part of that input. It is the base of each relPath and therefore also of each file id.

Pattern That Validates an Entry

The source parameter of the Origin annotation type validates one entry with this pattern:

^[A-Za-z0-9_]+:([1-9][0-9]*|[+](0|[1-9][0-9]*)|-[1-9][0-9]*):[1-9][0-9]*(~[A-Za-z0-9_-]{6}\.[A-Za-z0-9_-]{6})?$

The block gives the regular expression itself and not its spelling in a file. A .def.json5 file holds the expression in a string, so each backslash of it needs a second backslash there, and \. is \\. in that file. [+] avoids the question for the plus sign, because a character class needs no backslash on either level.

The pattern gives the canonical form of each number, so a leading zero and the form -0 do not match.

The pattern validates only the shape of one entry. A regular expression cannot do four other checks. It cannot find out if a delta resolves. It cannot find out if an id is in the table. It cannot find out if an anchor is still correct. It cannot find out if two entries of one object use the same id. It can express the limit of 2147483647 of a number, but not in a readable way, so that check also belongs to the parser.

Each value from the generator MUST match this pattern. The generator writes one shape only, always with the anchor, and the shape without an anchor is for a transitive entry of an author.

The format before version 1 did not have this property. Its pattern accepted only a full L:C-L:C shape, while the generator also wrote a L:C shape and a L:C-C shape, so a value of the generator did not validate.

Conformance

A generator is conformant if all these statements are true:

  • A file with an _origin annotation has a $originSpec object, also when the producer wrote no origin of its own.

  • Each file entry is an object with exactly one of relPath and absPath.

  • Each relPath value is relative to the folder of the file that holds the header and is not absolute. A path that comes from an input file has the base of the export file and not the base of that input file.

  • Each relPath value is in its shortest form, without a ./ at the start, without a . segment, without a .. segment after a name and without a slash at the end.

  • Each path value uses a forward slash and holds the characters that the file system gives, without a conversion to NFC.

  • Each entry that could use relPath does use it. An absPath value occurs only where no relative path exists.

  • The files table holds one entry for each file that an _origin annotation of the file names, and its other entries follow a rule that the annotations do not change.

  • Confµgami makes each file id from the complete set of files of the table, and never from the sequence in which it found them. A file id is not an index number and matches [A-Za-z0-9_]+. The prefix of a .default.def.json(5) file and of a .preconfig.def.json(5) file holds its role. A file that shares its prefix with another file of the table carries the digest of its own path, and no part of a path of a different file.

  • Each annotation without a parent object for its file id is absolute.

  • Each delta is relative to the nearest parent object with an origin for the same file id.

  • Each line number and each column number is the number of the rules for reading the file.

  • Each column number is at the start of a UTF-8 character. The first column is column 1.

  • Each number is in its canonical form, without a leading zero, a delta of zero is +0, and no number is larger than 2147483647.

  • Each traced entry has an anchor.

  • No entry holds an end position.

  • Each value matches the pattern.

  • An array of origins starts with the weakest source and stops with the strongest source. The sequence of the sources is the only rule that builds it, and no entry moves for any other reason. Each transitive origin that is in the array is directly after its own source.

  • No object has two origins with the same file id. Where two sources named one upstream file, the entry of the strongest source is the entry that stayed.

  • The producer re-derived the file ids, then reduced each object, and then chose the line form, in that sequence.

  • No lineRef of an input file is copied. The export resolved each transitive entry against the tree of its own input file, and then chose the form against the tree of the export.

  • The output has an indentation, a stable sequence of the keys and one annotation on each line.

  • Two runs with the same input give the same output, byte for byte.

The digest has its own tests. See Conformance Tests of the Anchor.

Rejected Alternatives

Alternative Why we did not use it

An absolute line number in each annotation

One new line at the top of a source file changes each annotation for that file.

The end of the element in each entry, as an offset from the start line and an end column

The end line of an object is the end line of its last child, so a new property of a leaf element changes the entry of each object above it, and the entry of the root object of a file then changes for each edit anywhere in that file. Those objects did not move: their start, their identity and their anchor are unchanged, and the format still rewrote their annotation. That is the second design goal, and the end was the one part of the format that broke it.

The end is also the one part of an entry that a consumer can never check, because the anchor covers the start line only. It was therefore the least reliable value of an entry and the largest cause of changes in it. A consumer that needs the end of a traced element has the source file open at that point and can read the end from it, and a range of an element is not what a consumer of this format looks for.

A sign in place of the separator between the file id and the line, as in A+2:5

The sign belongs to the line and not to the separator, and the hyphen then has two meanings inside one entry. A colon between each pair of fields costs one octet in a delta entry and gives one rule for reading an entry.

An array of files with an index number

A new file or a removed file changes each index number.

The name of a parent folder to make a colliding file id unique

The id of a file then holds a part of a path of a different file, so the producer must repeat the derivation until each id is unique, and must also compare against the ids outside the group. A digest of the own path of the file needs one step and no comparison.

One entry for each source when two sources name one upstream file, with a marker for the source that an entry belongs to

The marker is a new part of the grammar, and each consumer must then read it. The entry of the weakest source is reachable without it, through the annotation of that source, which is one step further.

A digest in each file id, and not only in a colliding one

A new file then changes no other id at all, which is better than the rule of this format. But each id is then unreadable, also in a table where no name occurs two times, and that is the usual table.

A plain string as the file entry

A later version cannot add a property to it. The change from a string to an object rewrites each line of the table.

A delta relative to the sequence in the export file

The sequence in the export file does not always follow the sequence in the source file.

A delta relative to the parent entity, and not to the parent object

The export file must then have a marker for an entity. The JSON has no such marker.

A separate table with a JSON Pointer for each key

A new element in an array changes each key below it.

One block of data in the format of a source map

This is the smallest format. But each change makes a new block, because it is one line.

A path relative to the first workspace root

The consumer must then know where that root is, and the export does not record it. A consumer that cannot run the producer has the export file only, and each path is then unresolvable for it. The producer of an input file must also know a root of a workspace that is not its own.

A root field with the workspace root

The value is specific to one machine. A path relative to the file with the header needs no such field.