| Age | Commit message (Collapse) | Author |
|---|
|
|
|
Otherwise we can get quadratic increase in size with deeply
nested structures.
See #355.
|
|
in accordance with spec change.
|
|
|
|
|
|
See #344.
|
|
|
|
This is illegal according to the C standard, sec. 7.1.4.
"If an argument to a function has an invalid value (such as a value
outside the domain of the function, or a pointer outside the address
space of the program, or a null pointer, or a pointer to non-modifiable
storage when the corresponding parameter is not const-qualified) or a
type (after promotion) not expected by a function with variable number
of arguments, the behavior is undefined."
7.24.1(2): "Where an argument declared as size_t n specifies the length
of the array for a function, n can have the value zero […] pointer
arguments on such a call shall still have valid values, as described in
7.1.4."
See https://www.imperialviolet.org/2016/06/26/nonnull.html
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
This reverts commit 54c990d17385156958556d86feca0c6e24da94e7.
|
|
|
|
This reverts commit abc45c57d368383eb05ca5fbb79d33b0370b419c.
|
|
|
|
|
|
|
|
This reverts commit 745b877835fed47e06daa3295aaf86312867f6f1.
|
|
|
|
This reverts commit c5732b26bb4d98cbec9de48cefad480cb880eb45.
|
|
|
|
|
|
|
|
|
|
This reverts commit 9f760cefdee9dbc18e6294d78d139b629062fad7.
|
|
|
|
|
|
|
|
|
|
|
|
Closes #334.
|
|
This is kivikakk's commit 62166fe3b6b07068ed4c4207113e3c4b060ad4a8
in cmark-gfm.
|
|
This commit ports Vicent Marti's fix in cmark-gfm.
(384cc9db4cd7a90f59c0751e58eb7b3023d38b85)
His commit message follows:
As explained on the previous commit, it is trivial to DoS the CMark
parser by generating a document where all the link reference names hash
to the same bucket in the hash table.
This will cause the lookup process for each reference to take linear
time on the amount of references in the document, and with enough link
references to lookup, the end result is a pathological O(N^2) that
causes medium-sized documents to finish parsing in 5+ minutes.
To avoid this issue, we propose the present commit.
Based on the fact that all reference lookup/resolution in a Markdown
document is always performed as a last step during the parse process,
we've reimplemented reference storage as follows:
1. New references are always inserted at the end of a linked list. This
is an O(1) operation, and does not check whether an existing (duplicate)
reference with the same label already exists in the document.
2. Upon the first call to `cmark_reference_lookup` (when it is expected
that no further references will be added to the reference map), the
linked list of references is written into a fixed-size array.
3. The fixed size array can then be efficiently sorted in-place in O(n
log n). This operation only happens once. We perform this sort in a
_stable_ manner to ensure that the earliest link reference in the
document always has preference, as the spec dictates. To accomplish
this, every reference is tagged with a generation number when initially
inserted in the linked list.
4. The sorted array is then compacted in O(n). Since it was sorted in a
stable way, the first reference for each label is preserved and the
duplicates are removed, matching the spec.
5. We can now simply perform a binary search for the current
`cmark_reference_lookup` query in O(log n). Any further lookup calls
will also be O(log n), since the sorted references table only needs to
be generated once.
The resulting implementation is notably simple (as it uses standard
library builtins `qsort` and `bsearch`), whilst performing better than
the fixed size hash table in documents that have a high number of
references and never becoming pathological regardless of the input.
|
|
This is taken from GitHub's fix:
https://github.com/github/cmark-gfm/commit/66a0836dc91e1653f7931e1218446664493da520
|
|
|
|
Closes #332.
|
