Home | History | Annotate | Download | only in util 
      1 /*
      2  * Copyright (C) 2017 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 #pragma clang diagnostic push
     18 #pragma clang diagnostic ignored "-Wunused-parameter"
     19 #pragma clang diagnostic ignored "-Wunused-variable"
     20 #pragma clang diagnostic ignored "-Wunused-value"
     21 
     22 #define C2_LOG_VERBOSE
     23 
     24 #include <C2Debug.h>
     25 #include <C2Param.h>
     26 #include <C2ParamDef.h>
     27 #include <C2ParamInternal.h>
     28 #include <util/C2InterfaceUtils.h>
     29 
     30 #include <cmath>
     31 #include <limits>
     32 #include <map>
     33 #include <type_traits>
     34 
     35 #include <android-base/stringprintf.h>
     36 
     37 std::ostream& operator<<(std::ostream& os, const _C2FieldId &i);
     38 
     39 std::ostream& operator<<(std::ostream& os, const C2ParamField &i);
     40 
     41 /* ---------------------------- C2SupportedRange ---------------------------- */
     42 
     43 /**
     44  * Helper class for supported values range calculations.
     45  */
     46 template<typename T, bool FP=std::is_floating_point<T>::value>
     47 struct _C2TypedSupportedRangeHelper {
     48     /**
     49      * type of range size: a - b if a >= b and a and b are of type T
     50      */
     51     typedef typename std::make_unsigned<T>::type DiffType;
     52 
     53     /**
     54      * calculate (high - low) mod step
     55      */
     56     static DiffType mod(T low, T high, T step) {
     57         return DiffType(high - low) % DiffType(step);
     58     }
     59 };
     60 
     61 template<typename T>
     62 struct _C2TypedSupportedRangeHelper<T, true> {
     63     typedef T DiffType;
     64 
     65     static DiffType mod(T low, T high, T step) {
     66         return fmod(high - low, step);
     67     }
     68 };
     69 
     70 template<typename T>
     71 C2SupportedRange<T>::C2SupportedRange(const C2FieldSupportedValues &values) {
     72     if (values.type == C2FieldSupportedValues::RANGE) {
     73         _mMin = values.range.min.ref<ValueType>();
     74         _mMax = values.range.max.ref<ValueType>();
     75         _mStep = values.range.step.ref<ValueType>();
     76         _mNum = values.range.num.ref<ValueType>();
     77         _mDenom = values.range.denom.ref<ValueType>();
     78     } else {
     79         _mMin = MAX_VALUE;
     80         _mMax = MIN_VALUE;
     81         _mStep = MIN_STEP;
     82         _mNum = 0;
     83         _mDenom = 0;
     84     }
     85 }
     86 
     87 template<typename T>
     88 bool C2SupportedRange<T>::contains(T value) const {
     89     // value must fall between min and max
     90     if (value < _mMin || value > _mMax) {
     91         return false;
     92     }
     93     // simple ranges contain all values between min and max
     94     if (isSimpleRange()) {
     95         return true;
     96     }
     97     // min is always part of the range
     98     if (value == _mMin) {
     99         return true;
    100     }
    101     // stepped ranges require (val - min) % step to be zero
    102     if (isArithmeticSeries()) {
    103         return _C2TypedSupportedRangeHelper<T>::mod(_mMin, value, _mStep) == 0;
    104     }
    105     // pure geometric series require (val / min) to be integer multiple of (num/denom)
    106     if (isGeometricSeries()) {
    107         if (value <= 0) {
    108             return false;
    109         }
    110         double log2base = log2(_mNum / _mDenom);
    111         double power = llround(log2(value / double(_mMin)) / log2base);
    112         // TODO: validate that result falls within precision (other than round)
    113         return value == T(_mMin * pow(_mNum / _mDenom, power) + MIN_STEP / 2);
    114     }
    115     // multiply-accumulate series require validating by walking through the series
    116     if (isMacSeries()) {
    117         double lastValue = _mMin;
    118         double base = _mNum / _mDenom;
    119         while (true) {
    120             // this cast is safe as _mMin <= lastValue <= _mMax
    121             if (T(lastValue + MIN_STEP / 2) == value) {
    122                 return true;
    123             }
    124             double nextValue = fma(lastValue, base, _mStep);
    125             if (nextValue <= lastValue || nextValue > _mMax) {
    126                 return false; // series is no longer monotonic or within range
    127             }
    128             lastValue = nextValue;
    129         };
    130     }
    131     // if we are here, this must be an invalid range
    132     return false;
    133 }
    134 
    135 template<typename T>
    136 C2SupportedRange<T> C2SupportedRange<T>::limitedTo(const C2SupportedRange<T> &limit) const {
    137     // TODO - this only works for simple ranges
    138     return C2SupportedRange(std::max(_mMin, limit._mMin), std::min(_mMax, limit._mMax),
    139                                  std::max(_mStep, limit._mStep));
    140 }
    141 
    142 template class C2SupportedRange<uint8_t>;
    143 template class C2SupportedRange<char>;
    144 template class C2SupportedRange<int32_t>;
    145 template class C2SupportedRange<uint32_t>;
    146 //template class C2SupportedRange<c2_cntr32_t>;
    147 template class C2SupportedRange<int64_t>;
    148 template class C2SupportedRange<uint64_t>;
    149 //template class C2SupportedRange<c2_cntr64_t>;
    150 template class C2SupportedRange<float>;
    151 
    152 /* -------------------------- C2SupportedFlags -------------------------- */
    153 
    154 /**
    155  * Ordered supported flag set for a field of a given type.
    156  */
    157 // float flags are not supported, but define a few methods to support generic supported values code
    158 template<>
    159 bool C2SupportedFlags<float>::contains(float value) const {
    160     return false;
    161 }
    162 
    163 template<>
    164 const std::vector<float> C2SupportedFlags<float>::flags() const {
    165     return std::vector<float>();
    166 }
    167 
    168 template<>
    169 C2SupportedFlags<float> C2SupportedFlags<float>::limitedTo(const C2SupportedFlags<float> &limit) const {
    170     std::vector<C2Value::Primitive> values;
    171     return C2SupportedFlags(std::move(values));
    172 }
    173 
    174 template<>
    175 float C2SupportedFlags<float>::min() const {
    176     return 0;
    177 }
    178 
    179 template<typename T>
    180 bool C2SupportedFlags<T>::contains(T value) const {
    181     // value must contain the minimal mask
    182     T minMask = min();
    183     if (~value & minMask) {
    184         return false;
    185     }
    186     value &= ~minMask;
    187     // otherwise, remove flags from value and see if we arrive at 0
    188     for (const C2Value::Primitive &v : _mValues) {
    189         if (value == 0) {
    190             break;
    191         }
    192         if ((~value & v.ref<ValueType>()) == 0) {
    193             value &= ~v.ref<ValueType>();
    194         }
    195     }
    196     return value == 0;
    197 }
    198 
    199 template<typename T>
    200 const std::vector<T> C2SupportedFlags<T>::flags() const {
    201     std::vector<T> vals(c2_max(_mValues.size(), 1u) - 1);
    202     if (!_mValues.empty()) {
    203         std::transform(_mValues.cbegin() + 1, _mValues.cend(), vals.begin(),
    204                        [](const C2Value::Primitive &p)->T {
    205             return p.ref<ValueType>();
    206         });
    207     }
    208     return vals;
    209 }
    210 
    211 template<typename T>
    212 C2SupportedFlags<T> C2SupportedFlags<T>::limitedTo(const C2SupportedFlags<T> &limit) const {
    213     std::vector<C2Value::Primitive> values = _mValues; // make a copy
    214     T minMask = min() | limit.min();
    215     // minimum mask must be covered by both this and other
    216     if (limit.contains(minMask) && contains(minMask)) {
    217         values[0] = minMask;
    218         // keep only flags that are covered by limit
    219         std::remove_if(values.begin(), values.end(), [&limit, minMask](const C2Value::Primitive &v) -> bool {
    220             T value = v.ref<ValueType>() | minMask;
    221             return value == minMask || !limit.contains(value); });
    222         // we also need to do it vice versa
    223         for (const C2Value::Primitive &v : _mValues) {
    224             T value = v.ref<ValueType>() | minMask;
    225             if (value != minMask && contains(value)) {
    226                 values.emplace_back((ValueType)value);
    227             }
    228         }
    229     }
    230     return C2SupportedFlags(std::move(values));
    231 }
    232 
    233 template<typename T>
    234 T C2SupportedFlags<T>::min() const {
    235     if (!_mValues.empty()) {
    236         return _mValues.front().template ref<ValueType>();
    237     } else {
    238         return T(0);
    239     }
    240 }
    241 
    242 template class C2SupportedFlags<uint8_t>;
    243 template class C2SupportedFlags<char>;
    244 template class C2SupportedFlags<int32_t>;
    245 template class C2SupportedFlags<uint32_t>;
    246 //template class C2SupportedFlags<c2_cntr32_t>;
    247 template class C2SupportedFlags<int64_t>;
    248 template class C2SupportedFlags<uint64_t>;
    249 //template class C2SupportedFlags<c2_cntr64_t>;
    250 
    251 /* -------------------------- C2SupportedValueSet -------------------------- */
    252 
    253 /**
    254  * Ordered supported value set for a field of a given type.
    255  */
    256 template<typename T>
    257 bool C2SupportedValueSet<T>::contains(T value) const {
    258     return std::find_if(_mValues.cbegin(), _mValues.cend(),
    259             [value](const C2Value::Primitive &p) -> bool {
    260                 return value == p.ref<ValueType>();
    261             }) != _mValues.cend();
    262 }
    263 
    264 template<typename T>
    265 C2SupportedValueSet<T> C2SupportedValueSet<T>::limitedTo(const C2SupportedValueSet<T> &limit) const {
    266     std::vector<C2Value::Primitive> values = _mValues; // make a copy
    267     std::remove_if(values.begin(), values.end(), [&limit](const C2Value::Primitive &v) -> bool {
    268         return !limit.contains(v.ref<ValueType>()); });
    269     return C2SupportedValueSet(std::move(values));
    270 }
    271 
    272 template<typename T>
    273 C2SupportedValueSet<T> C2SupportedValueSet<T>::limitedTo(const C2SupportedRange<T> &limit) const {
    274     std::vector<C2Value::Primitive> values = _mValues; // make a copy
    275     std::remove_if(values.begin(), values.end(), [&limit](const C2Value::Primitive &v) -> bool {
    276         return !limit.contains(v.ref<ValueType>()); });
    277     return C2SupportedValueSet(std::move(values));
    278 }
    279 
    280 template<typename T>
    281 C2SupportedValueSet<T> C2SupportedValueSet<T>::limitedTo(const C2SupportedFlags<T> &limit) const {
    282     std::vector<C2Value::Primitive> values = _mValues; // make a copy
    283     std::remove_if(values.begin(), values.end(), [&limit](const C2Value::Primitive &v) -> bool {
    284         return !limit.contains(v.ref<ValueType>()); });
    285     return C2SupportedValueSet(std::move(values));
    286 }
    287 
    288 template<typename T>
    289 const std::vector<T> C2SupportedValueSet<T>::values() const {
    290     std::vector<T> vals(_mValues.size());
    291     std::transform(_mValues.cbegin(), _mValues.cend(), vals.begin(), [](const C2Value::Primitive &p) -> T {
    292         return p.ref<ValueType>();
    293     });
    294     return vals;
    295 }
    296 
    297 template class C2SupportedValueSet<uint8_t>;
    298 template class C2SupportedValueSet<char>;
    299 template class C2SupportedValueSet<int32_t>;
    300 template class C2SupportedValueSet<uint32_t>;
    301 //template class C2SupportedValueSet<c2_cntr32_t>;
    302 template class C2SupportedValueSet<int64_t>;
    303 template class C2SupportedValueSet<uint64_t>;
    304 //template class C2SupportedValueSet<c2_cntr64_t>;
    305 template class C2SupportedValueSet<float>;
    306 
    307 /* ---------------------- C2FieldSupportedValuesHelper ---------------------- */
    308 
    309 template<typename T>
    310 struct C2FieldSupportedValuesHelper<T>::Impl {
    311     Impl(const C2FieldSupportedValues &values)
    312         : _mType(values.type),
    313           _mRange(values),
    314           _mValues(values),
    315           _mFlags(values) { }
    316 
    317     bool supports(T value) const;
    318 
    319 private:
    320     typedef typename _C2FieldValueHelper<T>::ValueType ValueType;
    321     C2FieldSupportedValues::type_t _mType;
    322     C2SupportedRange<ValueType> _mRange;
    323     C2SupportedValueSet<ValueType> _mValues;
    324     C2SupportedValueSet<ValueType> _mFlags;
    325 
    326 //    friend std::ostream& operator<< <T>(std::ostream& os, const C2FieldSupportedValuesHelper<T>::Impl &i);
    327 //    friend std::ostream& operator<<(std::ostream& os, const Impl &i);
    328     std::ostream& streamOut(std::ostream& os) const;
    329 };
    330 
    331 template<typename T>
    332 bool C2FieldSupportedValuesHelper<T>::Impl::supports(T value) const {
    333     switch (_mType) {
    334         case C2FieldSupportedValues::RANGE: return _mRange.contains(value);
    335         case C2FieldSupportedValues::VALUES: return _mValues.contains(value);
    336         case C2FieldSupportedValues::FLAGS: return _mFlags.contains(value);
    337         default: return false;
    338     }
    339 }
    340 
    341 template<typename T>
    342 C2FieldSupportedValuesHelper<T>::C2FieldSupportedValuesHelper(const C2FieldSupportedValues &values)
    343     : _mImpl(std::make_unique<C2FieldSupportedValuesHelper<T>::Impl>(values)) { }
    344 
    345 template<typename T>
    346 C2FieldSupportedValuesHelper<T>::~C2FieldSupportedValuesHelper() = default;
    347 
    348 template<typename T>
    349 bool C2FieldSupportedValuesHelper<T>::supports(T value) const {
    350     return _mImpl->supports(value);
    351 }
    352 
    353 template class C2FieldSupportedValuesHelper<uint8_t>;
    354 template class C2FieldSupportedValuesHelper<char>;
    355 template class C2FieldSupportedValuesHelper<int32_t>;
    356 template class C2FieldSupportedValuesHelper<uint32_t>;
    357 //template class C2FieldSupportedValuesHelper<c2_cntr32_t>;
    358 template class C2FieldSupportedValuesHelper<int64_t>;
    359 template class C2FieldSupportedValuesHelper<uint64_t>;
    360 //template class C2FieldSupportedValuesHelper<c2_cntr64_t>;
    361 template class C2FieldSupportedValuesHelper<float>;
    362 
    363 /* ----------------------- C2ParamFieldValuesBuilder ----------------------- */
    364 
    365 template<typename T>
    366 struct C2ParamFieldValuesBuilder<T>::Impl {
    367     Impl(const C2ParamField &field)
    368         : _mParamField(field),
    369           _mType(type_t::RANGE),
    370           _mDefined(false),
    371           _mRange(C2SupportedRange<T>::Any()),
    372           _mValues(C2SupportedValueSet<T>::None()),
    373           _mFlags(C2SupportedFlags<T>::None()) { }
    374 
    375     /**
    376      * Get C2ParamFieldValues from this builder.
    377      */
    378     operator C2ParamFieldValues() const {
    379         if (!_mDefined) {
    380             return C2ParamFieldValues(_mParamField);
    381         }
    382         switch (_mType) {
    383         case type_t::EMPTY:
    384         case type_t::VALUES:
    385             return C2ParamFieldValues(_mParamField, (C2FieldSupportedValues)_mValues);
    386         case type_t::RANGE:
    387             return C2ParamFieldValues(_mParamField, (C2FieldSupportedValues)_mRange);
    388         case type_t::FLAGS:
    389             return C2ParamFieldValues(_mParamField, (C2FieldSupportedValues)_mFlags);
    390         default:
    391             // TRESPASS
    392             // should never get here
    393             return C2ParamFieldValues(_mParamField);
    394         }
    395     }
    396 
    397     /** Define the supported values as the currently supported values of this builder. */
    398     void any() {
    399         _mDefined = true;
    400     }
    401 
    402     /** Restrict (and thus define) the supported values to none. */
    403     void none() {
    404         _mDefined = true;
    405         _mType = type_t::VALUES;
    406         _mValues.clear();
    407     }
    408 
    409     /** Restrict (and thus define) the supported values to |value| alone. */
    410     void equalTo(T value) {
    411          return limitTo(C2SupportedValueSet<T>::OneOf({value}));
    412     }
    413 
    414     /** Restrict (and thus define) the supported values to a value set. */
    415     void limitTo(const C2SupportedValueSet<T> &limit) {
    416         if (!_mDefined) {
    417             C2_LOG(VERBOSE) << "NA.limitTo(" << C2FieldSupportedValuesHelper<T>(limit) << ")";
    418 
    419             // shortcut for first limit applied
    420             _mDefined = true;
    421             _mValues = limit;
    422             _mType = _mValues.isEmpty() ? type_t::EMPTY : type_t::VALUES;
    423         } else {
    424             switch (_mType) {
    425             case type_t::EMPTY:
    426             case type_t::VALUES:
    427                 C2_LOG(VERBOSE) << "(" << C2FieldSupportedValuesHelper<T>(_mValues) << ").limitTo("
    428                         << C2FieldSupportedValuesHelper<T>(limit) << ")";
    429 
    430                 _mValues = _mValues.limitedTo(limit);
    431                 _mType = _mValues.isEmpty() ? type_t::EMPTY : type_t::VALUES;
    432                 break;
    433             case type_t::RANGE:
    434                 C2_LOG(VERBOSE) << "(" << C2FieldSupportedValuesHelper<T>(_mRange) << ").limitTo("
    435                         << C2FieldSupportedValuesHelper<T>(limit) << ")";
    436 
    437                 _mValues = limit.limitedTo(_mRange);
    438                 _mType = _mValues.isEmpty() ? type_t::EMPTY : type_t::VALUES;
    439                 break;
    440             case type_t::FLAGS:
    441                 C2_LOG(VERBOSE) << "(" << C2FieldSupportedValuesHelper<T>(_mRange) << ").limitTo("
    442                         << C2FieldSupportedValuesHelper<T>(limit) << ")";
    443 
    444                 _mValues = limit.limitedTo(_mFlags);
    445                 _mType = _mValues.isEmpty() ? type_t::EMPTY : type_t::VALUES;
    446                 break;
    447             default:
    448                 C2_LOG(FATAL); // should not be here
    449             }
    450             // TODO: support flags
    451         }
    452         C2_LOG(VERBOSE) << " = " << _mType << ":" << C2FieldSupportedValuesHelper<T>(_mValues);
    453     }
    454 
    455     /** Restrict (and thus define) the supported values to a flag set. */
    456     void limitTo(const C2SupportedFlags<T> &limit) {
    457         if (!_mDefined) {
    458             C2_LOG(VERBOSE) << "NA.limitTo(" << C2FieldSupportedValuesHelper<T>(limit) << ")";
    459 
    460             // shortcut for first limit applied
    461             _mDefined = true;
    462             _mFlags = limit;
    463             _mType = _mFlags.isEmpty() ? type_t::EMPTY : type_t::FLAGS;
    464         } else {
    465             switch (_mType) {
    466             case type_t::EMPTY:
    467             case type_t::VALUES:
    468                 C2_LOG(VERBOSE) << "(" << C2FieldSupportedValuesHelper<T>(_mValues) << ").limitTo("
    469                         << C2FieldSupportedValuesHelper<T>(limit) << ")";
    470 
    471                 _mValues = _mValues.limitedTo(limit);
    472                 _mType = _mValues.isEmpty() ? type_t::EMPTY : type_t::VALUES;
    473                 C2_LOG(VERBOSE) << " = " << _mType << ":" << C2FieldSupportedValuesHelper<T>(_mValues);
    474                 break;
    475             case type_t::FLAGS:
    476                 C2_LOG(VERBOSE) << "(" << C2FieldSupportedValuesHelper<T>(_mFlags) << ").limitTo("
    477                         << C2FieldSupportedValuesHelper<T>(limit) << ")";
    478 
    479                 _mFlags = _mFlags.limitedTo(limit);
    480                 _mType = _mFlags.isEmpty() ? type_t::EMPTY : type_t::FLAGS;
    481                 C2_LOG(VERBOSE) << " = " << _mType << ":" << C2FieldSupportedValuesHelper<T>(_mFlags);
    482                 break;
    483             case type_t::RANGE:
    484                 C2_LOG(FATAL) << "limiting ranges to flags is not supported";
    485                 _mType = type_t::EMPTY;
    486                 break;
    487             default:
    488                 C2_LOG(FATAL); // should not be here
    489             }
    490         }
    491     }
    492 
    493     void limitTo(const C2SupportedRange<T> &limit) {
    494         if (!_mDefined) {
    495             C2_LOG(VERBOSE) << "NA.limitTo(" << C2FieldSupportedValuesHelper<T>(limit) << ")";
    496 
    497             // shortcut for first limit applied
    498             _mDefined = true;
    499             _mRange = limit;
    500             _mType = _mRange.isEmpty() ? type_t::EMPTY : type_t::RANGE;
    501             C2_LOG(VERBOSE) << " = " << _mType << ":" << C2FieldSupportedValuesHelper<T>(_mRange);
    502         } else {
    503             switch (_mType) {
    504             case type_t::EMPTY:
    505             case type_t::VALUES:
    506                 C2_LOG(VERBOSE) << "(" << C2FieldSupportedValuesHelper<T>(_mValues) << ").limitTo("
    507                         << C2FieldSupportedValuesHelper<T>(limit) << ")";
    508                 _mValues = _mValues.limitedTo(limit);
    509                 _mType = _mValues.isEmpty() ? type_t::EMPTY : type_t::VALUES;
    510                 C2_LOG(VERBOSE) << " = " << _mType << ":" << C2FieldSupportedValuesHelper<T>(_mValues);
    511                 break;
    512             case type_t::FLAGS:
    513                 C2_LOG(FATAL) << "limiting flags to ranges is not supported";
    514                 _mType = type_t::EMPTY;
    515                 break;
    516             case type_t::RANGE:
    517                 C2_LOG(VERBOSE) << "(" << C2FieldSupportedValuesHelper<T>(_mRange) << ").limitTo("
    518                         << C2FieldSupportedValuesHelper<T>(limit) << ")";
    519                 _mRange = _mRange.limitedTo(limit);
    520                 C2_DCHECK(_mValues.isEmpty());
    521                 _mType = _mRange.isEmpty() ? type_t::EMPTY : type_t::RANGE;
    522                 C2_LOG(VERBOSE) << " = " << _mType << ":" << C2FieldSupportedValuesHelper<T>(_mRange);
    523                 break;
    524             default:
    525                 C2_LOG(FATAL); // should not be here
    526             }
    527         }
    528     }
    529 
    530 private:
    531     void instantiate() __unused {
    532         (void)_mValues.values(); // instantiate non-const values()
    533     }
    534 
    535     void instantiate() const __unused {
    536         (void)_mValues.values(); // instantiate const values()
    537     }
    538 
    539     typedef C2FieldSupportedValues::type_t type_t;
    540 
    541     C2ParamField _mParamField;
    542     type_t _mType;
    543     bool _mDefined;
    544     C2SupportedRange<T> _mRange;
    545     C2SupportedValueSet<T> _mValues;
    546     C2SupportedFlags<T> _mFlags;
    547 
    548 };
    549 
    550 template<typename T>
    551 C2ParamFieldValuesBuilder<T>::operator C2ParamFieldValues() const {
    552     return (C2ParamFieldValues)(*_mImpl.get());
    553 }
    554 
    555 template<typename T>
    556 C2ParamFieldValuesBuilder<T>::C2ParamFieldValuesBuilder(const C2ParamField &field)
    557     : _mImpl(std::make_unique<C2ParamFieldValuesBuilder<T>::Impl>(field)) { }
    558 
    559 template<typename T>
    560 C2ParamFieldValuesBuilder<T> &C2ParamFieldValuesBuilder<T>::any() {
    561     _mImpl->any();
    562     return *this;
    563 }
    564 
    565 template<typename T>
    566 C2ParamFieldValuesBuilder<T> &C2ParamFieldValuesBuilder<T>::none() {
    567     _mImpl->none();
    568     return *this;
    569 }
    570 
    571 template<typename T>
    572 C2ParamFieldValuesBuilder<T> &C2ParamFieldValuesBuilder<T>::equalTo(T value) {
    573     _mImpl->equalTo(value);
    574     return *this;
    575 }
    576 
    577 template<typename T>
    578 C2ParamFieldValuesBuilder<T> &C2ParamFieldValuesBuilder<T>::limitTo(const C2SupportedValueSet<T> &limit) {
    579     _mImpl->limitTo(limit);
    580     return *this;
    581 }
    582 
    583 template<typename T>
    584 C2ParamFieldValuesBuilder<T> &C2ParamFieldValuesBuilder<T>::limitTo(const C2SupportedFlags<T> &limit) {
    585     _mImpl->limitTo(limit);
    586     return *this;
    587 }
    588 
    589 template<typename T>
    590 C2ParamFieldValuesBuilder<T> &C2ParamFieldValuesBuilder<T>::limitTo(const C2SupportedRange<T> &limit) {
    591     _mImpl->limitTo(limit);
    592     return *this;
    593 }
    594 
    595 template<typename T>
    596 C2ParamFieldValuesBuilder<T>::C2ParamFieldValuesBuilder(const C2ParamFieldValuesBuilder<T> &other)
    597     : _mImpl(std::make_unique<C2ParamFieldValuesBuilder<T>::Impl>(*other._mImpl.get())) { }
    598 
    599 template<typename T>
    600 C2ParamFieldValuesBuilder<T> &C2ParamFieldValuesBuilder<T>::operator=(
    601         const C2ParamFieldValuesBuilder<T> &other) {
    602     _mImpl = std::make_unique<C2ParamFieldValuesBuilder<T>::Impl>(*other._mImpl.get());
    603     return *this;
    604 }
    605 
    606 template<typename T>
    607 C2ParamFieldValuesBuilder<T>::~C2ParamFieldValuesBuilder() = default;
    608 
    609 template class C2ParamFieldValuesBuilder<uint8_t>;
    610 template class C2ParamFieldValuesBuilder<char>;
    611 template class C2ParamFieldValuesBuilder<int32_t>;
    612 template class C2ParamFieldValuesBuilder<uint32_t>;
    613 //template class C2ParamFieldValuesBuilder<c2_cntr32_t>;
    614 template class C2ParamFieldValuesBuilder<int64_t>;
    615 template class C2ParamFieldValuesBuilder<uint64_t>;
    616 //template class C2ParamFieldValuesBuilder<c2_cntr64_t>;
    617 template class C2ParamFieldValuesBuilder<float>;
    618 
    619 /* ------------------------- C2SettingResultBuilder ------------------------- */
    620 
    621 C2SettingConflictsBuilder::C2SettingConflictsBuilder() : _mConflicts() { }
    622 
    623 C2SettingConflictsBuilder::C2SettingConflictsBuilder(C2ParamFieldValues &&conflict) {
    624     _mConflicts.emplace_back(std::move(conflict));
    625 }
    626 
    627 C2SettingConflictsBuilder& C2SettingConflictsBuilder::with(C2ParamFieldValues &&conflict) {
    628     _mConflicts.emplace_back(std::move(conflict));
    629     return *this;
    630 }
    631 
    632 std::vector<C2ParamFieldValues> C2SettingConflictsBuilder::retrieveConflicts() {
    633     return std::move(_mConflicts);
    634 }
    635 
    636 /* ------------------------- C2SettingResult/sBuilder ------------------------- */
    637 
    638 C2SettingResult C2SettingResultBuilder::ReadOnly(const C2ParamField &param) {
    639     return C2SettingResult { C2SettingResult::READ_ONLY, { param }, { } };
    640 }
    641 
    642 C2SettingResult C2SettingResultBuilder::BadValue(const C2ParamField &paramField, bool isInfo) {
    643     return { isInfo ? C2SettingResult::INFO_BAD_VALUE : C2SettingResult::BAD_VALUE,
    644              { paramField }, { } };
    645 }
    646 
    647 C2SettingResult C2SettingResultBuilder::Conflict(
    648         C2ParamFieldValues &&paramFieldValues, C2SettingConflictsBuilder &conflicts, bool isInfo) {
    649     C2_CHECK(!conflicts.empty());
    650     if (isInfo) {
    651         return C2SettingResult {
    652             C2SettingResult::INFO_CONFLICT,
    653             std::move(paramFieldValues), conflicts.retrieveConflicts()
    654         };
    655     } else {
    656         return C2SettingResult {
    657             C2SettingResult::CONFLICT,
    658             std::move(paramFieldValues), conflicts.retrieveConflicts()
    659         };
    660     }
    661 }
    662 
    663 C2SettingResultsBuilder::C2SettingResultsBuilder(C2SettingResult &&result)
    664         : _mStatus(C2_BAD_VALUE) {
    665     _mResults.emplace_back(new C2SettingResult(std::move(result)));
    666 }
    667 
    668 C2SettingResultsBuilder C2SettingResultsBuilder::plus(C2SettingResultsBuilder&& results) {
    669     for (std::unique_ptr<C2SettingResult> &r : results._mResults) {
    670         _mResults.emplace_back(std::move(r));
    671     }
    672     results._mResults.clear();
    673     // TODO: mStatus
    674     return std::move(*this);
    675 }
    676 
    677 c2_status_t C2SettingResultsBuilder::retrieveFailures(
    678         std::vector<std::unique_ptr<C2SettingResult>>* const failures) {
    679     for (std::unique_ptr<C2SettingResult> &r : _mResults) {
    680         failures->emplace_back(std::move(r));
    681     }
    682     _mResults.clear();
    683     return _mStatus;
    684 }
    685 
    686 C2SettingResultsBuilder::C2SettingResultsBuilder(c2_status_t status) : _mStatus(status) {
    687     // status must be one of OK, BAD_STATE, TIMED_OUT or CORRUPTED
    688     // mainly: BLOCKING, BAD_INDEX, BAD_VALUE and NO_MEMORY requires a setting attempt
    689 }
    690 
    691 #pragma clang diagnostic pop
    692 
    693 /* ------------------------- C2FieldUtils ------------------------- */
    694 
    695 struct C2_HIDE C2FieldUtils::_Inspector {
    696     /// returns the implementation object
    697     inline static std::shared_ptr<Info::Impl> GetImpl(const Info &info) {
    698         return info._mImpl;
    699     }
    700 };
    701 
    702 /* ------------------------- C2FieldUtils::Info ------------------------- */
    703 
    704 struct C2_HIDE C2FieldUtils::Info::Impl {
    705     C2FieldDescriptor field;
    706     std::shared_ptr<Impl> parent;
    707     uint32_t index;
    708     uint32_t depth;
    709     uint32_t baseFieldOffset;
    710     uint32_t arrayOffset;
    711     uint32_t usedExtent;
    712 
    713     /// creates a copy of this object including copies of its parent chain
    714     Impl clone() const;
    715 
    716     /// creates a copy of a shared pointer to an object
    717     static std::shared_ptr<Impl> Clone(const std::shared_ptr<Impl> &);
    718 
    719     Impl(const C2FieldDescriptor &field_, std::shared_ptr<Impl> parent_,
    720             uint32_t index_, uint32_t depth_, uint32_t baseFieldOffset_,
    721             uint32_t arrayOffset_, uint32_t usedExtent_)
    722         : field(field_), parent(parent_), index(index_), depth(depth_),
    723           baseFieldOffset(baseFieldOffset_), arrayOffset(arrayOffset_), usedExtent(usedExtent_) { }
    724 };
    725 
    726 std::shared_ptr<C2FieldUtils::Info::Impl> C2FieldUtils::Info::Impl::Clone(const std::shared_ptr<Impl> &info) {
    727     if (info) {
    728         return std::make_shared<Impl>(info->clone());
    729     }
    730     return nullptr;
    731 }
    732 
    733 C2FieldUtils::Info::Impl C2FieldUtils::Info::Impl::clone() const {
    734     Impl res = Impl(*this);
    735     res.parent = Clone(res.parent);
    736     return res;
    737 }
    738 
    739 C2FieldUtils::Info::Info(std::shared_ptr<Impl> impl)
    740     : _mImpl(impl) { }
    741 
    742 size_t C2FieldUtils::Info::arrayOffset() const {
    743     return _mImpl->arrayOffset;
    744 }
    745 
    746 size_t C2FieldUtils::Info::arraySize() const {
    747     return extent() * size();
    748 }
    749 
    750 size_t C2FieldUtils::Info::baseFieldOffset() const {
    751     return _mImpl->baseFieldOffset;
    752 };
    753 
    754 size_t C2FieldUtils::Info::depth() const {
    755     return _mImpl->depth;
    756 }
    757 
    758 size_t C2FieldUtils::Info::extent() const {
    759     return _mImpl->usedExtent;
    760 }
    761 
    762 size_t C2FieldUtils::Info::index() const {
    763     return _mImpl->index;
    764 }
    765 
    766 bool C2FieldUtils::Info::isArithmetic() const {
    767     switch (_mImpl->field.type()) {
    768     case C2FieldDescriptor::BLOB:
    769     case C2FieldDescriptor::CNTR32:
    770     case C2FieldDescriptor::CNTR64:
    771     case C2FieldDescriptor::FLOAT:
    772     case C2FieldDescriptor::INT32:
    773     case C2FieldDescriptor::INT64:
    774     case C2FieldDescriptor::STRING:
    775     case C2FieldDescriptor::UINT32:
    776     case C2FieldDescriptor::UINT64:
    777         return true;
    778     default:
    779         return false;
    780     }
    781 }
    782 
    783 bool C2FieldUtils::Info::isFlexible() const {
    784     return _mImpl->field.extent() == 0;
    785 }
    786 
    787 C2String C2FieldUtils::Info::name() const {
    788     return _mImpl->field.name();
    789 }
    790 
    791 const C2FieldUtils::Info::NamedValuesType &C2FieldUtils::Info::namedValues() const {
    792     return _mImpl->field.namedValues();
    793 }
    794 
    795 size_t C2FieldUtils::Info::offset() const {
    796     return _C2ParamInspector::GetOffset(_mImpl->field);
    797 }
    798 
    799 C2FieldUtils::Info C2FieldUtils::Info::parent() const {
    800     return Info(_mImpl->parent);
    801 };
    802 
    803 size_t C2FieldUtils::Info::size() const {
    804     return _C2ParamInspector::GetSize(_mImpl->field);
    805 }
    806 
    807 C2FieldUtils::Info::type_t C2FieldUtils::Info::type() const {
    808     return _mImpl->field.type();
    809 }
    810 
    811 /* ------------------------- C2FieldUtils::Iterator ------------------------- */
    812 
    813 struct C2_HIDE C2FieldUtils::Iterator::Impl : public _C2ParamInspector {
    814     Impl() = default;
    815 
    816     virtual ~Impl() = default;
    817 
    818     /// implements object equality
    819     virtual bool equals(const std::shared_ptr<Impl> &other) const {
    820         return other != nullptr && mHead == other->mHead;
    821     };
    822 
    823     /// returns the info pointed to by this iterator
    824     virtual value_type get() const {
    825         return Info(mHead);
    826     }
    827 
    828     /// increments this iterator
    829     virtual void increment() {
    830         // note: this cannot be abstract as we instantiate this for List::end(). increment to end()
    831         // instead.
    832         mHead.reset();
    833     }
    834 
    835 protected:
    836     Impl(std::shared_ptr<C2FieldUtils::Info::Impl> head)
    837         : mHead(head) { }
    838 
    839     std::shared_ptr<Info::Impl> mHead; ///< current field
    840 };
    841 
    842 C2FieldUtils::Iterator::Iterator(std::shared_ptr<Impl> impl)
    843     : mImpl(impl) { }
    844 
    845 C2FieldUtils::Iterator::value_type C2FieldUtils::Iterator::operator*() const {
    846     return mImpl->get();
    847 }
    848 
    849 C2FieldUtils::Iterator& C2FieldUtils::Iterator::operator++() {
    850     mImpl->increment();
    851     return *this;
    852 }
    853 
    854 bool C2FieldUtils::Iterator::operator==(const Iterator &other) const {
    855     return mImpl->equals(other.mImpl);
    856 }
    857 
    858 /* ------------------------- C2FieldUtils::List ------------------------- */
    859 
    860 struct C2_HIDE C2FieldUtils::List::Impl {
    861     virtual std::shared_ptr<Iterator::Impl> begin() const = 0;
    862 
    863     /// returns an iterator to the end of the list
    864     virtual std::shared_ptr<Iterator::Impl> end() const {
    865         return std::make_shared<Iterator::Impl>();
    866     }
    867 
    868     virtual ~Impl() = default;
    869 };
    870 
    871 C2FieldUtils::List::List(std::shared_ptr<Impl> impl)
    872     : mImpl(impl) { }
    873 
    874 C2FieldUtils::Iterator C2FieldUtils::List::begin() const {
    875     return C2FieldUtils::Iterator(mImpl->begin());
    876 }
    877 
    878 C2FieldUtils::Iterator C2FieldUtils::List::end() const {
    879     return C2FieldUtils::Iterator(mImpl->end());
    880 }
    881 
    882 /* ------------------------- C2FieldUtils::enumerateFields ------------------------- */
    883 
    884 namespace {
    885 
    886 /**
    887  * Iterator base class helper that allows descending into the field hierarchy.
    888  */
    889 struct C2FieldUtilsFieldsIteratorHelper : public C2FieldUtils::Iterator::Impl {
    890     virtual ~C2FieldUtilsFieldsIteratorHelper() override = default;
    891 
    892     /// returns the base-field's offset of the parent field (or the param offset if no parent)
    893     static inline uint32_t GetParentBaseFieldOffset(
    894             const std::shared_ptr<C2FieldUtils::Info::Impl> parent) {
    895         return parent == nullptr ? sizeof(C2Param) : parent->baseFieldOffset;
    896     }
    897 
    898     /// returns the offset of the parent field (or the param)
    899     static inline uint32_t GetParentOffset(const std::shared_ptr<C2FieldUtils::Info::Impl> parent) {
    900         return parent == nullptr ? sizeof(C2Param) : GetOffset(parent->field);
    901     }
    902 
    903 protected:
    904     C2FieldUtilsFieldsIteratorHelper(
    905             std::shared_ptr<C2ParamReflector> reflector,
    906             uint32_t paramSize,
    907             std::shared_ptr<C2FieldUtils::Info::Impl> head = nullptr)
    908         : C2FieldUtils::Iterator::Impl(head),
    909           mParamSize(paramSize),
    910           mReflector(reflector) { }
    911 
    912     /// returns a leaf info object at a specific index for a child field
    913     std::shared_ptr<C2FieldUtils::Info::Impl> makeLeaf(
    914             const C2FieldDescriptor &field, uint32_t index) {
    915         uint32_t parentOffset = GetParentOffset(mHead);
    916         uint32_t arrayOffset = parentOffset + GetOffset(field);
    917         uint32_t usedExtent = field.extent() ? :
    918                 (std::max(arrayOffset, mParamSize) - arrayOffset) / GetSize(field);
    919 
    920         return std::make_shared<C2FieldUtils::Info::Impl>(
    921                 OffsetFieldDescriptor(field, parentOffset + index * GetSize(field)),
    922                 mHead /* parent */, index, mHead == nullptr ? 0 : mHead->depth + 1,
    923                 GetParentBaseFieldOffset(mHead) + GetOffset(field),
    924                 arrayOffset, usedExtent);
    925     }
    926 
    927     /// returns whether this struct index have been traversed to get to this field
    928     bool visited(C2Param::CoreIndex index) const {
    929         for (const std::shared_ptr<C2StructDescriptor> &sd : mHistory) {
    930             if (sd->coreIndex() == index) {
    931                 return true;
    932             }
    933         }
    934         return false;
    935     }
    936 
    937     uint32_t mParamSize;
    938     std::shared_ptr<C2ParamReflector> mReflector;
    939     std::vector<std::shared_ptr<C2StructDescriptor>> mHistory; // structure types visited
    940 };
    941 
    942 /**
    943  * Iterator implementing enumerateFields() that visits each base field.
    944  */
    945 struct C2FieldUtilsFieldsIterator : public C2FieldUtilsFieldsIteratorHelper {
    946     /// enumerate base fields of a parameter
    947     C2FieldUtilsFieldsIterator(const C2Param &param, std::shared_ptr<C2ParamReflector> reflector)
    948         : C2FieldUtilsFieldsIteratorHelper(reflector, param.size()) {
    949         descendInto(param.coreIndex());
    950     }
    951 
    952     /// enumerate base fields of a field
    953     C2FieldUtilsFieldsIterator(std::shared_ptr<C2FieldUtilsFieldsIterator> impl)
    954         : C2FieldUtilsFieldsIteratorHelper(impl->mReflector, impl->mParamSize, impl->mHead) {
    955         mHistory = impl->mHistory;
    956         if (mHead->field.type() & C2FieldDescriptor::STRUCT_FLAG) {
    957             C2Param::CoreIndex index = { mHead->field.type() &~C2FieldDescriptor::STRUCT_FLAG };
    958             if (!visited(index)) {
    959                 descendInto(index);
    960             }
    961         }
    962     }
    963 
    964     virtual ~C2FieldUtilsFieldsIterator() override = default;
    965 
    966     /// Increments this iterator by visiting each base field.
    967     virtual void increment() override {
    968         // don't go past end
    969         if (mHead == nullptr || _mFields.empty()) {
    970             return;
    971         }
    972 
    973         // descend into structures
    974         if (mHead->field.type() & C2FieldDescriptor::STRUCT_FLAG) {
    975             C2Param::CoreIndex index = { mHead->field.type() &~C2FieldDescriptor::STRUCT_FLAG };
    976             // do not recurse into the same structs
    977             if (!visited(index) && descendInto(index)) {
    978                 return;
    979             }
    980         }
    981 
    982         // ascend after the last field in the current struct
    983         while (!mHistory.empty() && _mFields.back() == mHistory.back()->end()) {
    984             mHead = mHead->parent;
    985             mHistory.pop_back();
    986             _mFields.pop_back();
    987         }
    988 
    989         // done if history is now empty
    990         if (_mFields.empty()) {
    991             // we could be traversing a sub-tree so clear head
    992             mHead.reset();
    993             return;
    994         }
    995 
    996         // move to the next field in the current struct
    997         C2StructDescriptor::field_iterator next = _mFields.back();
    998         mHead->field = OffsetFieldDescriptor(*next, GetParentOffset(mHead->parent));
    999         mHead->index = 0; // reset index just in case for correctness
   1000         mHead->baseFieldOffset = GetParentBaseFieldOffset(mHead->parent) + GetOffset(*next);
   1001         mHead->arrayOffset = GetOffset(mHead->field);
   1002         mHead->usedExtent = mHead->field.extent() ? :
   1003                 (std::max(mHead->arrayOffset, mParamSize) - mHead->arrayOffset)
   1004                         / GetSize(mHead->field);
   1005         ++_mFields.back();
   1006     }
   1007 
   1008 private:
   1009     /// If the current field is a known, valid (untraversed) structure, it modifies this iterator
   1010     /// to point to the first field of the structure and returns true. Otherwise, it does not
   1011     /// modify this iterator and returns false.
   1012     bool descendInto(C2Param::CoreIndex index) {
   1013         std::unique_ptr<C2StructDescriptor> descUnique = mReflector->describe(index);
   1014         // descend into known structs (as long as they have at least one field)
   1015         if (descUnique && descUnique->begin() != descUnique->end()) {
   1016             std::shared_ptr<C2StructDescriptor> desc(std::move(descUnique));
   1017             mHistory.emplace_back(desc);
   1018             C2StructDescriptor::field_iterator first = desc->begin();
   1019             mHead = makeLeaf(*first, 0 /* index */);
   1020             _mFields.emplace_back(++first);
   1021             return true;
   1022         }
   1023         return false;
   1024     }
   1025 
   1026     /// next field pointers for each depth.
   1027     /// note: _mFields may be shorted than mHistory, if iterating at a depth
   1028     std::vector<C2StructDescriptor::field_iterator> _mFields;
   1029 };
   1030 
   1031 /**
   1032  * Iterable implementing enumerateFields().
   1033  */
   1034 struct C2FieldUtilsFieldIterable : public C2FieldUtils::List::Impl {
   1035     /// returns an iterator to the beginning of the list
   1036     virtual std::shared_ptr<C2FieldUtils::Iterator::Impl> begin() const override {
   1037         return std::make_shared<C2FieldUtilsFieldsIterator>(*_mParam, _mReflector);
   1038     };
   1039 
   1040     C2FieldUtilsFieldIterable(const C2Param &param, std::shared_ptr<C2ParamReflector> reflector)
   1041         : _mParam(&param), _mReflector(reflector) { }
   1042 
   1043 private:
   1044     const C2Param *_mParam;
   1045     std::shared_ptr<C2ParamReflector> _mReflector;
   1046 };
   1047 
   1048 }
   1049 
   1050 C2FieldUtils::List C2FieldUtils::enumerateFields(
   1051         const C2Param &param, const std::shared_ptr<C2ParamReflector> &reflector) {
   1052     return C2FieldUtils::List(std::make_shared<C2FieldUtilsFieldIterable>(param, reflector));
   1053 }
   1054 
   1055 /* ------------------------- C2FieldUtils::enumerate siblings ------------------------- */
   1056 
   1057 namespace {
   1058 
   1059 struct C2FieldUtilsCousinsIterator : public C2FieldUtils::Iterator::Impl {
   1060     C2FieldUtilsCousinsIterator(
   1061                 const std::shared_ptr<C2FieldUtils::Info::Impl> &info, size_t level)
   1062           // clone info chain as this iterator will change it
   1063         : C2FieldUtils::Iterator::Impl(C2FieldUtils::Info::Impl::Clone(info)) {
   1064         if (level == 0) {
   1065             return;
   1066         }
   1067 
   1068         // store parent chain (up to level) for quick access
   1069         std::shared_ptr<C2FieldUtils::Info::Impl> node = mHead;
   1070         size_t ix = 0;
   1071         for (; ix < level && node; ++ix) {
   1072             node->index = 0;
   1073             _mPath.emplace_back(node);
   1074             node = node->parent;
   1075         }
   1076         setupPath(ix);
   1077     }
   1078 
   1079     virtual ~C2FieldUtilsCousinsIterator() override = default;
   1080 
   1081     /// Increments this iterator by visiting each index.
   1082     virtual void increment() override {
   1083         size_t ix = 0;
   1084         while (ix < _mPath.size()) {
   1085             if (++_mPath[ix]->index < _mPath[ix]->usedExtent) {
   1086                 setupPath(ix + 1);
   1087                 return;
   1088             }
   1089             _mPath[ix++]->index = 0;
   1090         }
   1091         mHead.reset();
   1092     }
   1093 
   1094 private:
   1095     /// adjusts field offsets along the path up to the specific level - 1.
   1096     /// This in-fact has to be done down the path from parent to child as child fields must
   1097     /// fall within parent fields.
   1098     void setupPath(size_t level) {
   1099         C2_CHECK_LE(level, _mPath.size());
   1100         uint32_t oldArrayOffset = level ? _mPath[level - 1]->arrayOffset : 0 /* unused */;
   1101         while (level) {
   1102             --level;
   1103             C2FieldUtils::Info::Impl &path = *_mPath[level];
   1104             uint32_t size = GetSize(path.field);
   1105             uint32_t offset = path.arrayOffset + size * path.index;
   1106             SetOffset(path.field, offset);
   1107             if (level) {
   1108                 // reset child's array offset to fall within current index, but hold onto the
   1109                 // original value of the arrayOffset so that we can adjust subsequent children.
   1110                 // This is because the modulo is only defined within the current array.
   1111                 uint32_t childArrayOffset =
   1112                     offset + (_mPath[level - 1]->arrayOffset - oldArrayOffset) % size;
   1113                 oldArrayOffset = _mPath[level - 1]->arrayOffset;
   1114                 _mPath[level - 1]->arrayOffset = childArrayOffset;
   1115             }
   1116         }
   1117     }
   1118 
   1119     std::vector<std::shared_ptr<C2FieldUtils::Info::Impl>> _mPath;
   1120 };
   1121 
   1122 /**
   1123  * Iterable implementing enumerateFields().
   1124  */
   1125 struct C2FieldUtilsCousinsIterable : public C2FieldUtils::List::Impl {
   1126     /// returns an iterator to the beginning of the list
   1127     virtual std::shared_ptr<C2FieldUtils::Iterator::Impl> begin() const override {
   1128         return std::make_shared<C2FieldUtilsCousinsIterator>(_mHead, _mLevel);
   1129     };
   1130 
   1131     C2FieldUtilsCousinsIterable(const C2FieldUtils::Info &field, uint32_t level)
   1132         : _mHead(C2FieldUtils::_Inspector::GetImpl(field)), _mLevel(level) { }
   1133 
   1134 private:
   1135     std::shared_ptr<C2FieldUtils::Info::Impl> _mHead;
   1136     size_t _mLevel;
   1137 };
   1138 
   1139 }
   1140 
   1141 C2FieldUtils::List C2FieldUtils::enumerateCousins(const C2FieldUtils::Info &field, uint32_t level) {
   1142     return C2FieldUtils::List(std::make_shared<C2FieldUtilsCousinsIterable>(field, level));
   1143 }
   1144 
   1145 /* ------------------------- C2FieldUtils::locateField ------------------------- */
   1146 
   1147 namespace {
   1148 
   1149 /**
   1150  * Iterator implementing locateField().
   1151  */
   1152 struct C2FieldUtilsFieldLocator : public C2FieldUtilsFieldsIteratorHelper {
   1153     C2FieldUtilsFieldLocator(
   1154             C2Param::CoreIndex index, const _C2FieldId &field, uint32_t paramSize,
   1155             std::shared_ptr<C2ParamReflector> reflector)
   1156         : C2FieldUtilsFieldsIteratorHelper(reflector, paramSize),
   1157           _mField(field) {
   1158         while (descendInto(index)) {
   1159             if ((mHead->field.type() & C2FieldDescriptor::STRUCT_FLAG) == 0) {
   1160                 break;
   1161             }
   1162             index = C2Param::CoreIndex(mHead->field.type() &~ C2FieldDescriptor::STRUCT_FLAG);
   1163         }
   1164     }
   1165 
   1166     void increment() {
   1167         mHead = _mTail;
   1168         _mTail = nullptr;
   1169     }
   1170 
   1171 private:
   1172     /// If the current field is a known, valid (untraversed) structure, it modifies this iterator
   1173     /// to point to the field at the beginning/end of the given field of the structure and returns
   1174     /// true. Otherwise, including if no such field exists in the structure, it does not modify this
   1175     /// iterator and returns false.
   1176     bool descendInto(C2Param::CoreIndex index) {
   1177         // check that the boundaries of the field to be located are still within the same parent
   1178         // field
   1179         if (mHead != _mTail) {
   1180             return false;
   1181         }
   1182 
   1183         std::unique_ptr<C2StructDescriptor> descUnique = mReflector->describe(index);
   1184         // descend into known structs (as long as they have at least one field)
   1185         if (descUnique && descUnique->begin() != descUnique->end()) {
   1186             std::shared_ptr<C2StructDescriptor> desc(std::move(descUnique));
   1187             mHistory.emplace_back(desc);
   1188 
   1189             uint32_t parentOffset = GetParentOffset(mHead);
   1190 
   1191             // locate field using a dummy field descriptor
   1192             C2FieldDescriptor dummy = {
   1193                 C2FieldDescriptor::BLOB, 1 /* extent */, "name",
   1194                 GetOffset(_mField) - parentOffset, GetSize(_mField)
   1195             };
   1196 
   1197             // locate first field where offset is greater than dummy offset (which is one past)
   1198             auto it = std::upper_bound(
   1199                     desc->cbegin(), desc->cend(), dummy,
   1200                     [](const C2FieldDescriptor &a, const C2FieldDescriptor &b) -> bool {
   1201                 return _C2ParamInspector::GetOffset(a) < _C2ParamInspector::GetOffset(b);
   1202             });
   1203             if (it == desc->begin()) {
   1204                 // field is prior to first field
   1205                 return false;
   1206             }
   1207             --it;
   1208             const C2FieldDescriptor &field = *it;
   1209 
   1210             // check that dummy end-offset is within this field
   1211             uint32_t structSize = std::max(mParamSize, parentOffset) - parentOffset;
   1212             if (GetEndOffset(dummy) > GetEndOffset(field, structSize)) {
   1213                 return false;
   1214             }
   1215 
   1216             uint32_t startIndex = (GetOffset(dummy) - GetOffset(field)) / GetSize(field);
   1217             uint32_t endIndex =
   1218                 (GetEndOffset(dummy) - GetOffset(field) + GetSize(field) - 1) / GetSize(field);
   1219             if (endIndex > startIndex) {
   1220                 // Field size could be zero, in which case end index is still on start index.
   1221                 // However, for all other cases, endIndex was rounded up to the next index, so
   1222                 // decrement it.
   1223                 --endIndex;
   1224             }
   1225             std::shared_ptr<C2FieldUtils::Info::Impl> startLeaf =
   1226                 makeLeaf(field, startIndex);
   1227             if (endIndex == startIndex) {
   1228                 _mTail = startLeaf;
   1229                 mHead = startLeaf;
   1230             } else {
   1231                 _mTail = makeLeaf(field, endIndex);
   1232                 mHead = startLeaf;
   1233             }
   1234             return true;
   1235         }
   1236         return false;
   1237     }
   1238 
   1239     _C2FieldId _mField;
   1240     std::shared_ptr<C2FieldUtils::Info::Impl> _mTail;
   1241 };
   1242 
   1243 /**
   1244  * Iterable implementing locateField().
   1245  */
   1246 struct C2FieldUtilsFieldLocation : public C2FieldUtils::List::Impl {
   1247     /// returns an iterator to the beginning of the list
   1248     virtual std::shared_ptr<C2FieldUtils::Iterator::Impl> begin() const override {
   1249         return std::make_shared<C2FieldUtilsFieldLocator>(
   1250                 _mIndex, _mField, _mParamSize, _mReflector);
   1251     };
   1252 
   1253     C2FieldUtilsFieldLocation(
   1254             const C2ParamField &pf, std::shared_ptr<C2ParamReflector> reflector)
   1255         : _mIndex(C2Param::CoreIndex(_C2ParamInspector::GetIndex(pf))),
   1256           _mField(_C2ParamInspector::GetField(pf)),
   1257           _mParamSize(0),
   1258           _mReflector(reflector) { }
   1259 
   1260 
   1261     C2FieldUtilsFieldLocation(
   1262             const C2Param &param, const _C2FieldId &field,
   1263             std::shared_ptr<C2ParamReflector> reflector)
   1264         : _mIndex(param.coreIndex()),
   1265           _mField(field),
   1266           _mParamSize(param.size()),
   1267           _mReflector(reflector) { }
   1268 
   1269 private:
   1270     C2Param::CoreIndex _mIndex;
   1271     _C2FieldId _mField;
   1272     uint32_t _mParamSize;
   1273     std::shared_ptr<C2ParamReflector> _mReflector;
   1274 };
   1275 
   1276 }
   1277 
   1278 std::vector<C2FieldUtils::Info> C2FieldUtils::locateField(
   1279         const C2ParamField &pf, const std::shared_ptr<C2ParamReflector> &reflector) {
   1280     C2FieldUtils::List location = { std::make_shared<C2FieldUtilsFieldLocation>(pf, reflector) };
   1281     return std::vector<Info>(location.begin(), location.end());
   1282 }
   1283 
   1284 std::vector<C2FieldUtils::Info> C2FieldUtils::locateField(
   1285         const C2Param &param, const _C2FieldId &field,
   1286         const std::shared_ptr<C2ParamReflector> &reflector) {
   1287     C2FieldUtils::List location = {
   1288         std::make_shared<C2FieldUtilsFieldLocation>(param, field, reflector)
   1289     };
   1290     return std::vector<Info>(location.begin(), location.end());
   1291 }
   1292 
   1293