Correct doc & tests for mixed traversal in bounded maps (#191)
This does not change the behavior of QCBOR.
The changes the documentation to match the behavior. It also tests the behavior to make
sure it is correct.
The behavior at issue is where the traversal cursor ends up after fetching items by label in a map that has been entered. The retained behavior from QCBOR 1.2 is that fetching a non-aggregate does not affect the traversal cursor, but entering an aggregate sub map by label and exiting it does affect the traversal cursor.
The behavior is retained because it is usable, a change would bring backwards compatibility issues and the fix requires an increase in decode context size and in code complexity.
See also #149
* Correct doc & tests for mixed traversal in bounded maps
* straggler conflict marker
* Documentation updates
---------
Co-authored-by: Laurence Lundblade <lgl@securitytheory.com>
diff --git a/inc/qcbor/qcbor_spiffy_decode.h b/inc/qcbor/qcbor_spiffy_decode.h
index f2e1592..7423140 100644
--- a/inc/qcbor/qcbor_spiffy_decode.h
+++ b/inc/qcbor/qcbor_spiffy_decode.h
@@ -63,15 +63,36 @@
*
* When QCBORDecode_EnterMap() is called, pre-order traversal
* continues to work. There is a cursor that is run over the tree with
- * calls to QCBORDecode_GetNext(). This can be intermixed with calls
- * TODO: this is not quite true
- * to QCBORDecode_GetXxxxInMapX(). The pre-order traversal is limited
- * just to the map entered. Attempts to QCBORDecode_GetNext() beyond
- * the end of the map will give the @ref QCBOR_ERR_NO_MORE_ITEMS
- * error.
+ * calls to QCBORDecode_GetNext(). Attempts to use
+ * QCBORDecode_GetNext() beyond the end of the map will give the
+ * @ref QCBOR_ERR_NO_MORE_ITEMS error.
*
- * There is also QCBORDecode_EnterArray() to decode arrays. It will
- * narrow the traversal to the extent of the array entered.
+ * Use of the traversal cursor can be mixed with the fetching of items
+ * by label with some caveats. When a non-aggregate item like an
+ * integer or string is fetched by label, the traversal cursor is
+ * unaffected so the mixing can be done freely. When an aggregate
+ * item is entered by label (by QCBORDecode_EnterMapFromMapN() and
+ * similar), the traversal cursor is set to the item after the
+ * subordinate aggregate item when it is exited. This will not matter
+ * to many use cases. Use cases that mix can be sure to separate
+ * traversal by the cursor from fetching by label.
+ * QCBORDecode_Rewind() may be useful to reset the traversal cursor
+ * after fetching aggregate items by label.
+ *
+ * (This behavior was incorrectly documented in QCBOR 1.2 and prior
+ * which described aggregate and non-aggregate as behaving the same.
+ * Rather than changing to make aggregate and non-aggregate
+ * consistent, the behavior is retained and documented because 1) it
+ * is usable as is, 2) a change would bring backward compatibility
+ * issues, 3) the change would increase the decode context size and
+ * code size. In QCBOR 1.3 test cases were added to validate the
+ * behavior. No problems were uncovered.)
+ *
+ * QCBORDecode_EnterArray() can be used to narrow the traversal to the
+ * extent of the array.
+ *
+ * QCBORDecode_EnterArray() can be used to narrow the traversal to the
+ * extent of the array.
*
* All the QCBORDecode_GetXxxxInMapX() methods support duplicate label
* detection and will result in an error if the map has duplicate
@@ -81,11 +102,12 @@
* performing the pre-order traversal of the map to find the labeled
* item everytime it is called. It doesn't build up a hash table, a
* binary search tree or some other efficiently searchable structure
- * internally. For simple trees this is fine and for high-speed CPUs
- * this is fine, but for complex trees on slow CPUs, it may have
- * performance issues (these have not be quantified yet). One way ease
- * this is to use QCBORDecode_GetItemsInMap() which allows decoding of
- * a list of items expected in an map in one traveral.
+ * internally. For small maps this is fine and for high-speed CPUs
+ * this is fine, but for large, perhaps deeply nested, maps on slow
+ * CPUs, it may have performance issues (these have not be
+ * quantified). One way ease this is to use
+ * QCBORDecode_GetItemsInMap() which allows decoding of a list of
+ * items expected in an map in one traveral.
*
* @anchor Tag-Usage
* ## Tag Usage
@@ -718,12 +740,17 @@
* fully exited.
*
* While in bounded mode, QCBORDecode_GetNext() works as usual on the
- * map and the in-order traversal cursor is maintained. It starts out
+ * map and the pre-order traversal cursor is maintained. It starts out
* at the first item in the map just entered. Attempts to get items
* off the end of the map will give error @ref QCBOR_ERR_NO_MORE_ITEMS
* rather going to the next item after the map as it would when not in
* bounded mode.
*
+ * It is possible to mix use of the traversal cursor with the fetching
+ * of items in a map by label with the caveat that fetching
+ * non-aggregate items by label behaves differently from entering subordinate
+ * aggregate items by label. See dicussion in @ref SpiffyDecode.
+ *
* Exiting leaves the pre-order cursor at the data item following the
* last entry in the map or at the end of the input CBOR if there
* nothing after the map.
diff --git a/test/qcbor_decode_tests.c b/test/qcbor_decode_tests.c
index b3bf91d..05d2466 100644
--- a/test/qcbor_decode_tests.c
+++ b/test/qcbor_decode_tests.c
@@ -5727,6 +5727,109 @@
0xa1, 0x80, 0x00
};
+/*
+ Lots of nesting for various nesting tests.
+ { 1:1,
+ 2:{
+ 21:21,
+ 22:{
+ 221:[2111, 2112, 2113],
+ 222:222,
+ 223: {}
+ },
+ 23: 23
+ },
+ 3:3,
+ 4: [ {} ]
+ }
+ */
+static const uint8_t spNested[] = {
+0xA4, /* Map of 4 */
+ 0x01, 0x01, /* Map entry 1 : 1 */
+ 0x02, 0xA3, /* Map entry 2 : {, an array of 3 */
+ 0x15, 0x15, /* Map entry 21 : 21 */
+ 0x16, 0xA3, /* Map entry 22 : {, a map of 3 */
+ 0x18, 0xDD, 0x83, /* Map entry 221 : [ an array of 3 */
+ 0x19, 0x08, 0x3F, /* Array item 2111 */
+ 0x19, 0x08, 0x40, /* Array item 2112 */
+ 0x19, 0x08, 0x41, /* Array item 2113 */
+ 0x18, 0xDE, 0x18, 0xDE, /* Map entry 222 : 222 */
+ 0x18, 0xDF, 0xA0, /* Map entry 223 : {} */
+ 0x17, 0x17, /* Map entry 23 : 23 */
+ 0x03, 0x03, /* Map entry 3 : 3 */
+ 0x04, 0x81, /* Map entry 4: [, an array of 1 */
+ 0xA0 /* Array entry {}, an empty map */
+};
+
+
+static int32_t EnterMapCursorTest(void)
+{
+ QCBORDecodeContext DCtx;
+ QCBORItem Item1;
+
+ int i;
+ for(i = 0; i < 13; i++) {
+ QCBORDecode_Init(&DCtx, UsefulBuf_FROM_BYTE_ARRAY_LITERAL(spNested), 0);
+ QCBORDecode_EnterMap(&DCtx, NULL);
+ int j;
+ /* Move travesal cursor */
+ for(j = 0; j < i; j++) {
+ QCBORDecode_GetNext(&DCtx, &Item1);
+ }
+ QCBORDecode_EnterMapFromMapN(&DCtx, 2);
+ QCBORDecode_ExitMap(&DCtx);
+ QCBORDecode_GetNext(&DCtx, &Item1);
+ if(Item1.label.int64 != 3) {
+ return 8000;
+ }
+ }
+
+ for(i = 0; i < 13; i++) {
+ QCBORDecode_Init(&DCtx, UsefulBuf_FROM_BYTE_ARRAY_LITERAL(spNested), 0);
+ QCBORDecode_EnterMap(&DCtx, NULL);
+ int j;
+ /* Move travesal cursor */
+ for(j = 0; j < i; j++) {
+ QCBORDecode_GetNext(&DCtx, &Item1);
+ }
+ QCBORDecode_EnterMapFromMapN(&DCtx, 2);
+ QCBORDecode_EnterMapFromMapN(&DCtx, 22);
+ QCBORDecode_ExitMap(&DCtx);
+ QCBORDecode_GetNext(&DCtx, &Item1);
+ if(Item1.label.int64 != 23) {
+ return 8000;
+ }
+ }
+
+ for(i = 0; i < 13; i++) {
+ QCBORDecode_Init(&DCtx, UsefulBuf_FROM_BYTE_ARRAY_LITERAL(spNested), 0);
+ QCBORDecode_EnterMap(&DCtx, NULL);
+ int j;
+ /* Move travesal cursor */
+ for(j = 0; j < i; j++) {
+ QCBORDecode_GetNext(&DCtx, &Item1);
+ }
+ QCBORDecode_EnterMapFromMapN(&DCtx, 2);
+ QCBORDecode_EnterMapFromMapN(&DCtx, 22);
+ for(j = 0; j < i; j++) {
+ QCBORDecode_GetNext(&DCtx, &Item1);
+ }
+ QCBORDecode_EnterArrayFromMapN(&DCtx, 221);
+ QCBORDecode_ExitArray(&DCtx);
+ QCBORDecode_ExitMap(&DCtx);
+ QCBORDecode_GetNext(&DCtx, &Item1);
+ if(Item1.label.int64 != 23) {
+ return 8000;
+ }
+ QCBORDecode_ExitMap(&DCtx);
+ QCBORDecode_GetNext(&DCtx, &Item1);
+ if(Item1.label.int64 != 3) {
+ return 8000;
+ }
+ }
+
+ return 0;
+}
int32_t EnterMapTest(void)
@@ -6107,6 +6210,8 @@
return 3000;
}
+ nReturn = EnterMapCursorTest();
+
return nReturn;
}