folly/dynamic.h

   1 /*
   2  * Copyright 2016 Facebook, Inc.
   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 /**
  18  * This is a runtime dynamically typed value.  It holds types from a
  19  * specific predetermined set of types (ints, bools, arrays, etc).  In
  20  * particular, it can be used as a convenient in-memory representation
  21  * for complete json objects.
  22  *
  23  * In general you can try to use these objects as if they were the
  24  * type they represent (although in some cases with a slightly less
  25  * complete interface than the raw type), and it'll just throw a
  26  * TypeError if it is used in an illegal way.
  27  *
  28  * Some examples:
  29  *
  30  *   dynamic twelve = 12;
  31  *   dynamic str = "string";
  32  *   dynamic map = dynamic::object;
  33  *   map[str] = twelve;
  34  *   map[str + "another_str"] = dynamic::array("array", "of", 4, "elements");
  35  *   map.insert("null_element", nullptr);
  36  *   ++map[str];
  37  *   assert(map[str] == 13);
  38  *
  39  *   // Building a complex object with a sub array inline:
  40  *   dynamic d = dynamic::object
  41  *     ("key", "value")
  42  *     ("key2", dynamic::array("a", "array"))
  43  *     ;
  44  *
  45  * Also see folly/json.h for the serialization and deserialization
  46  * functions for JSON.
  47  *
  48  * Note: dynamic is not DefaultConstructible.  Rationale:
  49  *
  50  *   - The intuitive thing to initialize a defaulted dynamic to would
  51  *     be nullptr.
  52  *
  53  *   - However, the expression dynamic d = {} is required to call the
  54  *     default constructor by the standard, which is confusing
  55  *     behavior for dynamic unless the default constructor creates an
  56  *     empty array.
  57  *
  58  * Additional documentation is in folly/docs/Dynamic.md.
  59  *
  60  * @author Jordan DeLong <delong.j@fb.com>
  61  */
  62
  63 #pragma once
  64
  65 #include <cstdint>
  66 #include <initializer_list>
  67 #include <memory>
  68 #include <ostream>
  69 #include <string>
  70 #include <type_traits>
  71 #include <unordered_map>
  72 #include <utility>
  73 #include <vector>
  74
  75 #include <boost/operators.hpp>
  76
  77 #include <folly/FBString.h>
  78 #include <folly/Range.h>
  79 #include <folly/Traits.h>
  80
  81 namespace folly {
  82
  83 //////////////////////////////////////////////////////////////////////
  84
  85 struct dynamic;
  86 struct TypeError;
  87
  88 //////////////////////////////////////////////////////////////////////
  89
  90 struct dynamic : private boost::operators<dynamic> {
  91   enum Type {
  92     NULLT,
  93     ARRAY,
  94     BOOL,
  95     DOUBLE,
  96     INT64,
  97     OBJECT,
  98     STRING,
  99   };
 100
 101   /*
 102    * We support direct iteration of arrays, and indirect iteration of objects.
 103    * See begin(), end(), keys(), values(), and items() for more.
 104    *
 105    * Array iterators dereference as the elements in the array.
 106    * Object key iterators dereference as the keys in the object.
 107    * Object value iterators dereference as the values in the object.
 108    * Object item iterators dereference as pairs of (key, value).
 109    */
 110 private:
 111   typedef std::vector<dynamic> Array;
 112 public:
 113   typedef Array::const_iterator const_iterator;
 114   typedef dynamic value_type;
 115   struct const_key_iterator;
 116   struct const_value_iterator;
 117   struct const_item_iterator;
 118
 119   /*
 120    * Creation routines for making dynamic objects and arrays.  Objects
 121    * are maps from key to value (so named due to json-related origins
 122    * here).
 123    *
 124    * Example:
 125    *
 126    *   // Make a fairly complex dynamic:
 127    *   dynamic d = dynamic::object("key", "value1")
 128    *                              ("key2", dynamic::array("value",
 129    *                                                      "with",
 130    *                                                      4,
 131    *                                                      "words"));
 132    *
 133    *   // Build an object in a few steps:
 134    *   dynamic d = dynamic::object;
 135    *   d["key"] = 12;
 136    *   d["something_else"] = dynamic::array(1, 2, 3, nullptr);
 137    */
 138 private:
 139   struct PrivateTag {};
 140   struct EmptyArrayTag {};
 141   struct ObjectMaker;
 142
 143 public:
 144   static void array(EmptyArrayTag);
 145   template <class... Args>
 146   static dynamic array(Args&& ...args);
 147
 148   static ObjectMaker object();
 149   static ObjectMaker object(dynamic&&, dynamic&&);
 150   static ObjectMaker object(dynamic const&, dynamic&&);
 151   static ObjectMaker object(dynamic&&, dynamic const&);
 152   static ObjectMaker object(dynamic const&, dynamic const&);
 153
 154   /*
 155    * String compatibility constructors.
 156    */
 157   /* implicit */ dynamic(StringPiece val);
 158   /* implicit */ dynamic(char const* val);
 159   /* implicit */ dynamic(std::string const& val);
 160   /* implicit */ dynamic(fbstring const& val);
 161   /* implicit */ dynamic(fbstring&& val);
 162
 163   /*
 164    * This is part of the plumbing for array() and object(), above.
 165    * Used to create a new array or object dynamic.
 166    */
 167   /* implicit */ dynamic(void (*)(EmptyArrayTag));
 168   /* implicit */ dynamic(ObjectMaker (*)());
 169   /* implicit */ dynamic(ObjectMaker const&) = delete;
 170   /* implicit */ dynamic(ObjectMaker&&);
 171
 172   /*
 173    * Create a new array from an initializer list.
 174    *
 175    * For example:
 176    *
 177    *   dynamic v = { 1, 2, 3, "foo" };
 178    */
 179   // TODO(ott, 10300209): Remove once all uses have been eradicated.
 180
 181   FOLLY_DEPRECATED(
 182       "Initializer list syntax is deprecated (#10300209). Use dynamic::array.")
 183   /* implicit */ dynamic(std::initializer_list<dynamic> il);
 184   dynamic(std::initializer_list<dynamic> il, PrivateTag);
 185   FOLLY_DEPRECATED(
 186       "Initializer list syntax is deprecated (#10300209). Use dynamic::array.")
 187   dynamic& operator=(std::initializer_list<dynamic> il);
 188
 189   /*
 190    * Conversion constructors from most of the other types.
 191    */
 192   template<class T> /* implicit */ dynamic(T t);
 193
 194   /*
 195    * Create a dynamic that is an array of the values from the supplied
 196    * iterator range.
 197    */
 198   template<class Iterator> dynamic(Iterator first, Iterator last);
 199
 200   dynamic(dynamic const&);
 201   dynamic(dynamic&&) noexcept;
 202   ~dynamic() noexcept;
 203
 204   /*
 205    * "Deep" equality comparison.  This will compare all the way down
 206    * an object or array, and is potentially expensive.
 207    */
 208   bool operator==(dynamic const& o) const;
 209
 210   /*
 211    * For all types except object this returns the natural ordering on
 212    * those types.  For objects, we throw TypeError.
 213    */
 214   bool operator<(dynamic const& o) const;
 215
 216   /*
 217    * General operators.
 218    *
 219    * These throw TypeError when used with types or type combinations
 220    * that don't support them.
 221    *
 222    * These functions may also throw if you use 64-bit integers with
 223    * doubles when the integers are too big to fit in a double.
 224    */
 225   dynamic& operator+=(dynamic const&);
 226   dynamic& operator-=(dynamic const&);
 227   dynamic& operator*=(dynamic const&);
 228   dynamic& operator/=(dynamic const&);
 229   dynamic& operator%=(dynamic const&);
 230   dynamic& operator|=(dynamic const&);
 231   dynamic& operator&=(dynamic const&);
 232   dynamic& operator^=(dynamic const&);
 233   dynamic& operator++();
 234   dynamic& operator--();
 235
 236   /*
 237    * Assignment from other dynamics.  Because of the implicit conversion
 238    * to dynamic from its potential types, you can use this to change the
 239    * type pretty intuitively.
 240    *
 241    * Basic guarantee only.
 242    */
 243   dynamic& operator=(dynamic const&);
 244   dynamic& operator=(dynamic&&) noexcept;
 245
 246   /*
 247    * For simple dynamics (not arrays or objects), this prints the
 248    * value to an std::ostream in the expected way.  Respects the
 249    * formatting manipulators that have been sent to the stream
 250    * already.
 251    *
 252    * If the dynamic holds an object or array, this prints them in a
 253    * format very similar to JSON.  (It will in fact actually be JSON
 254    * as long as the dynamic validly represents a JSON object---i.e. it
 255    * can't have non-string keys.)
 256    */
 257   friend std::ostream& operator<<(std::ostream&, dynamic const&);
 258
 259   /*
 260    * Returns true if this dynamic is of the specified type.
 261    */
 262   bool isString() const;
 263   bool isObject() const;
 264   bool isBool() const;
 265   bool isNull() const;
 266   bool isArray() const;
 267   bool isDouble() const;
 268   bool isInt() const;
 269
 270   /*
 271    * Returns: isInt() || isDouble().
 272    */
 273   bool isNumber() const;
 274
 275   /*
 276    * Returns the type of this dynamic.
 277    */
 278   Type type() const;
 279
 280   /*
 281    * Returns the type of this dynamic as a printable string.
 282    */
 283   const char* typeName() const;
 284
 285   /*
 286    * Extract a value while trying to convert to the specified type.
 287    * Throws exceptions if we cannot convert from the real type to the
 288    * requested type.
 289    *
 290    * Note you can only use this to access integral types or strings,
 291    * since arrays and objects are generally best dealt with as a
 292    * dynamic.
 293    */
 294   fbstring asString() const;
 295   double   asDouble() const;
 296   int64_t  asInt() const;
 297   bool     asBool() const;
 298
 299   /*
 300    * Extract the value stored in this dynamic without type conversion.
 301    *
 302    * These will throw a TypeError if the dynamic has a different type.
 303    */
 304   const fbstring& getString() const&;
 305   double          getDouble() const&;
 306   int64_t         getInt() const&;
 307   bool            getBool() const&;
 308   fbstring& getString() &;
 309   double&   getDouble() &;
 310   int64_t&  getInt() &;
 311   bool&     getBool() &;
 312   fbstring getString() &&;
 313   double   getDouble() &&;
 314   int64_t  getInt() &&;
 315   bool     getBool() &&;
 316
 317   /*
 318    * It is occasionally useful to access a string's internal pointer
 319    * directly, without the type conversion of `asString()`.
 320    *
 321    * These will throw a TypeError if the dynamic is not a string.
 322    */
 323   const char* data()  const&;
 324   const char* data()  && = delete;
 325   const char* c_str() const&;
 326   const char* c_str() && = delete;
 327   StringPiece stringPiece() const;
 328
 329   /*
 330    * Returns: true if this dynamic is null, an empty array, an empty
 331    * object, or an empty string.
 332    */
 333   bool empty() const;
 334
 335   /*
 336    * If this is an array or an object, returns the number of elements
 337    * contained.  If it is a string, returns the length.  Otherwise
 338    * throws TypeError.
 339    */
 340   std::size_t size() const;
 341
 342   /*
 343    * You can iterate over the values of the array.  Calling these on
 344    * non-arrays will throw a TypeError.
 345    */
 346   const_iterator begin()  const;
 347   const_iterator end()    const;
 348
 349 private:
 350   /*
 351    * Helper object returned by keys(), values(), and items().
 352    */
 353   template <class T> struct IterableProxy;
 354
 355 public:
 356   /*
 357    * You can iterate over the keys, values, or items (std::pair of key and
 358    * value) in an object.  Calling these on non-objects will throw a TypeError.
 359    */
 360   IterableProxy<const_key_iterator> keys() const;
 361   IterableProxy<const_value_iterator> values() const;
 362   IterableProxy<const_item_iterator> items() const;
 363
 364   /*
 365    * AssociativeContainer-style find interface for objects.  Throws if
 366    * this is not an object.
 367    *
 368    * Returns: items().end() if the key is not present, or a
 369    * const_item_iterator pointing to the item.
 370    */
 371   const_item_iterator find(dynamic const&) const;
 372
 373   /*
 374    * If this is an object, returns whether it contains a field with
 375    * the given name.  Otherwise throws TypeError.
 376    */
 377   std::size_t count(dynamic const&) const;
 378
 379   /*
 380    * For objects or arrays, provides access to sub-fields by index or
 381    * field name.
 382    *
 383    * Using these with dynamic objects that are not arrays or objects
 384    * will throw a TypeError.  Using an index that is out of range or
 385    * object-element that's not present throws std::out_of_range.
 386    */
 387   dynamic const& at(dynamic const&) const&;
 388   dynamic&       at(dynamic const&) &;
 389   dynamic        at(dynamic const&) &&;
 390
 391   /*
 392    * Like 'at', above, except it returns either a pointer to the contained
 393    * object or nullptr if it wasn't found. This allows a key to be tested for
 394    * containment and retrieved in one operation. Example:
 395    *
 396    *   if (auto* found = d.get_ptr(key))
 397    *     // use *found;
 398    *
 399    * Using these with dynamic objects that are not arrays or objects
 400    * will throw a TypeError.
 401    */
 402   const dynamic* get_ptr(dynamic const&) const&;
 403   dynamic* get_ptr(dynamic const&) &;
 404   dynamic* get_ptr(dynamic const&) && = delete;
 405
 406   /*
 407    * This works for access to both objects and arrays.
 408    *
 409    * In the case of an array, the index must be an integer, and this will throw
 410    * std::out_of_range if it is less than zero or greater than size().
 411    *
 412    * In the case of an object, the non-const overload inserts a null
 413    * value if the key isn't present.  The const overload will throw
 414    * std::out_of_range if the key is not present.
 415    *
 416    * These functions do not invalidate iterators.
 417    */
 418   dynamic&       operator[](dynamic const&) &;
 419   dynamic const& operator[](dynamic const&) const&;
 420   dynamic        operator[](dynamic const&) &&;
 421
 422   /*
 423    * Only defined for objects, throws TypeError otherwise.
 424    *
 425    * getDefault will return the value associated with the supplied key, the
 426    * supplied default otherwise. setDefault will set the key to the supplied
 427    * default if it is not yet set, otherwise leaving it. setDefault returns
 428    * a reference to the existing value if present, the new value otherwise.
 429    */
 430   dynamic
 431   getDefault(const dynamic& k, const dynamic& v = dynamic::object) const&;
 432   dynamic getDefault(const dynamic& k, dynamic&& v) const&;
 433   dynamic getDefault(const dynamic& k, const dynamic& v = dynamic::object) &&;
 434   dynamic getDefault(const dynamic& k, dynamic&& v) &&;
 435   template<class K, class V = dynamic>
 436   dynamic& setDefault(K&& k, V&& v = dynamic::object);
 437
 438   /*
 439    * Resizes an array so it has at n elements, using the supplied
 440    * default to fill new elements.  Throws TypeError if this dynamic
 441    * is not an array.
 442    *
 443    * May invalidate iterators.
 444    *
 445    * Post: size() == n
 446    */
 447   void resize(std::size_t n, dynamic const& = nullptr);
 448
 449   /*
 450    * Inserts the supplied key-value pair to an object, or throws if
 451    * it's not an object.
 452    *
 453    * Invalidates iterators.
 454    */
 455   template<class K, class V> void insert(K&&, V&& val);
 456
 457   /*
 458    * These functions merge two folly dynamic objects.
 459    * The "update" and "update_missing" functions extend the object by
 460    *  inserting the key/value pairs of mergeObj into the current object.
 461    *  For update, if key is duplicated between the two objects, it
 462    *  will overwrite with the value of the object being inserted (mergeObj).
 463    *  For "update_missing", it will prefer the value in the original object
 464    *
 465    * The "merge" function creates a new object consisting of the key/value
 466    * pairs of both mergeObj1 and mergeObj2
 467    * If the key is duplicated between the two objects,
 468    *  it will prefer value in the second object (mergeObj2)
 469    */
 470   void update(const dynamic& mergeObj);
 471   void update_missing(const dynamic& other);
 472   static dynamic merge(const dynamic& mergeObj1, const dynamic& mergeObj2);
 473
 474   /*
 475    * Erase an element from a dynamic object, by key.
 476    *
 477    * Invalidates iterators to the element being erased.
 478    *
 479    * Returns the number of elements erased (i.e. 1 or 0).
 480    */
 481   std::size_t erase(dynamic const& key);
 482
 483   /*
 484    * Erase an element from a dynamic object or array, using an
 485    * iterator or an iterator range.
 486    *
 487    * In arrays, invalidates iterators to elements after the element
 488    * being erased.  In objects, invalidates iterators to the elements
 489    * being erased.
 490    *
 491    * Returns a new iterator to the first element beyond any elements
 492    * removed, or end() if there are none.  (The iteration order does
 493    * not change.)
 494    */
 495   const_iterator erase(const_iterator it);
 496   const_iterator erase(const_iterator first, const_iterator last);
 497
 498   const_key_iterator erase(const_key_iterator it);
 499   const_key_iterator erase(const_key_iterator first, const_key_iterator last);
 500
 501   const_value_iterator erase(const_value_iterator it);
 502   const_value_iterator erase(const_value_iterator first,
 503                              const_value_iterator last);
 504
 505   const_item_iterator erase(const_item_iterator it);
 506   const_item_iterator erase(const_item_iterator first,
 507                             const_item_iterator last);
 508   /*
 509    * Append elements to an array.  If this is not an array, throws
 510    * TypeError.
 511    *
 512    * Invalidates iterators.
 513    */
 514   void push_back(dynamic const&);
 515   void push_back(dynamic&&);
 516
 517   /*
 518    * Remove an element from the back of an array.  If this is not an array,
 519    * throws TypeError.
 520    *
 521    * Does not invalidate iterators.
 522    */
 523   void pop_back();
 524
 525   /*
 526    * Get a hash code.  This function is called by a std::hash<>
 527    * specialization, also.
 528    *
 529    * Throws TypeError if this is an object, array, or null.
 530    */
 531   std::size_t hash() const;
 532
 533 private:
 534   friend struct TypeError;
 535   struct ObjectImpl;
 536   template<class T> struct TypeInfo;
 537   template<class T> struct CompareOp;
 538   template<class T> struct GetAddrImpl;
 539   template<class T> struct PrintImpl;
 540
 541   template<class T> T const& get() const;
 542   template<class T> T&       get();
 543   template<class T> T*       get_nothrow() & noexcept;
 544   template<class T> T const* get_nothrow() const& noexcept;
 545   template<class T> T*       get_nothrow() && noexcept = delete;
 546   template<class T> T*       getAddress() noexcept;
 547   template<class T> T const* getAddress() const noexcept;
 548
 549   template<class T> T asImpl() const;
 550
 551   static char const* typeName(Type);
 552   void destroy() noexcept;
 553   void print(std::ostream&) const;
 554   void print_as_pseudo_json(std::ostream&) const; // see json.cpp
 555
 556 private:
 557   Type type_;
 558   union Data {
 559     explicit Data() : nul(nullptr) {}
 560     ~Data() {}
 561
 562     // XXX: gcc does an ICE if we use std::nullptr_t instead of void*
 563     // here.  See http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50361
 564     void* nul;
 565     Array array;
 566     bool boolean;
 567     double doubl;
 568     int64_t integer;
 569     fbstring string;
 570
 571     /*
 572      * Objects are placement new'd here.  We have to use a char buffer
 573      * because we don't know the type here (std::unordered_map<> with
 574      * dynamic would be parameterizing a std:: template with an
 575      * incomplete type right now).  (Note that in contrast we know it
 576      * is ok to do this with fbvector because we own it.)
 577      */
 578     std::aligned_storage<
 579       sizeof(std::unordered_map<int,int>),
 580       alignof(std::unordered_map<int,int>)
 581     >::type objectBuffer;
 582   } u_;
 583 };
 584
 585 //////////////////////////////////////////////////////////////////////
 586
 587 }
 588
 589 #include <folly/dynamic-inl.h>