Skip to content

Commit 17f8a4e

Browse files
geofflangdalegeofflangdale
authored
Update Notes.md
1 parent 080a636 commit 17f8a4e

1 file changed

Lines changed: 6 additions & 14 deletions

File tree

‎Notes.md‎

Lines changed: 6 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -43,8 +43,7 @@ over bit vectors to discover backslash sequences and quote pairs; we introduce b
4343
these properties.
4444

4545
We also make use of our ability to quickly detect whitespace in this early stage. We can use another bit-vector based
46-
transformation to discover locations in our data that follow a structural character or quote followed by zero or more
47-
characters of whitespace; excluding locations within strings, and the structural characters we have already discovered,
46+
transformation to discover locations in our data that follow a structural character or quote or whitespace and are not whitesapce. Excluding locations within strings, and the structural characters we have already discovered,
4847
these locations are the only place that we can expect to see the starts of the JSON 'atoms'. These locations are thus
4948
treated as 'structural' ('pseudo-structural characters').
5049

@@ -77,17 +76,10 @@ for each bitmap.
7776

7877
### Stage 3: Operation over indices
7978

80-
The indices form a relatively concise map of structurally important parts of our JSON input. However, since JSON is
81-
recursively defined, we may nest structures (JSON "objects" and "arrays") inside other JSON structures. It is important
82-
to be able to quickly traverse portions of our JSON structure at any given level - it is trivial for us to move around
83-
in a way that follows the input text, but skipping to the next item at a given level may involve searching hundreds of
84-
bytes of text).
79+
This now works over a dual structure.
8580

86-
We can construct a simple data structure that allows us to thread together such structures relatively simply; at this
87-
stage this code is not branch-free. We use an implicit 'stack' structure by virtue of threading together 'up-level
88-
pointers' within the structure as we build it (these are pointers that, for each item in the structure we have seen
89-
already, tell us which item in the structure that contains this one); to pop up a level, we simply follow one layer
90-
of 'up-level pointers'.
81+
1. The "state machine", whose role it is to validate the sequence of structural characters and ensure that the input is at least generally structured like valid JSON (after this stage, the only errors permissible should be malformed atoms and numbers). If and only if the "state machine" reached all accept states, then,
9182

92-
An equivalent operation requiring an external data structure would be to maintain a stack that essentially describes
93-
all current levels of our structure as we traverse it; this may have performance advantages.
83+
2. The "tape machine" will have produced valid output. The tape machine works blindly over characters writing records to tapes. These records create a lean but somewhat traversable linked structure that, for valid inputs, should represent what we need to know about the JSON input.
84+
85+
FIXME: a lot more detail is required on the operation of both these machines.

0 commit comments

Comments
 (0)