text:
/*
 * Copyright © 2013  Google, Inc.
 *
 *  This is part of HarfBuzz, a text shaping library.
 *
 * Permission is hereby granted, without written agreement and without
 * license or royalty fees, to use, copy, modify, and distribute this
 * software and its documentation for any purpose, provided that the
 * above copyright notice and the following two paragraphs appear in
 * all copies of this software.
 *
 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
 * DAMAGE.
 *
 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
 * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
 *
 * Google Author(s): Behdad Esfahbod
 */

#include "hb.hh"

#ifndef HB_NO_OT_SHAPE

#include "hb-ot-shape-complex.hh"

/* Hangul shaper */

/* Same order as the feature array below */
enum {
  _JMO,

  LJMO,
  VJMO,
  TJMO,

  FIRST_HANGUL_FEATURE = LJMO,
  HANGUL_FEATURE_COUNT = TJMO + 1
};

static const hb_tag_t hangul_features[HANGUL_FEATURE_COUNT] =
{
  HB_TAG_NONE,
  HB_TAG('l','j','m','o'),
  HB_TAG('v','j','m','o'),
  HB_TAG('t','j','m','o')
};

static void
collect_features_hangul (hb_ot_shape_planner_t *plan)
{
  hb_ot_map_builder_t *map = &plan->map;

  for (unsigned int i = FIRST_HANGUL_FEATURE; i < HANGUL_FEATURE_COUNT; i++)
    map->add_feature (hangul_features[i]);
}

static void
override_features_hangul (hb_ot_shape_planner_t *plan)
{
  /* Uniscribe does not apply 'calt' for Hangul, and certain fonts
   * (Noto Sans CJK, Source Sans Han, etc) apply all of jamo lookups
   * in calt, which is not desirable. */
  plan->map.disable_feature (HB_TAG('c','a','l','t'));
}

struct hangul_shape_plan_t
{
  hb_mask_t mask_array[HANGUL_FEATURE_COUNT];
};

static void *
data_create_hangul (const hb_ot_shape_plan_t *plan)
{
  hangul_shape_plan_t *hangul_plan = (hangul_shape_plan_t *) calloc (1, sizeof (hangul_shape_plan_t));
  if (unlikely (!hangul_plan))
    return nullptr;

  for (unsigned int i = 0; i < HANGUL_FEATURE_COUNT; i++)
    hangul_plan->mask_array[i] = plan->map.get_1_mask (hangul_features[i]);

  return hangul_plan;
}

static void
data_destroy_hangul (void *data)
{
  free (data);
}

/* Constants for algorithmic hangul syllable [de]composition. */
#define LBase 0x1100u
#define VBase 0x1161u
#define TBase 0x11A7u
#define LCount 19u
#define VCount 21u
#define TCount 28u
#define SBase 0xAC00u
#define NCount (VCount * TCount)
#define SCount (LCount * NCount)

#define isCombiningL(u) (hb_in_range<hb_codepoint_t> ((u), LBase, LBase+LCount-1))
#define isCombiningV(u) (hb_in_range<hb_codepoint_t> ((u), VBase, VBase+VCount-1))
#define isCombiningT(u) (hb_in_range<hb_codepoint_t> ((u), TBase+1, TBase+TCount-1))
#define isCombinedS(u) (hb_in_range<hb_codepoint_t> ((u), SBase, SBase+SCount-1))

#define isL(u) (hb_in_ranges<hb_codepoint_t> ((u), 0x1100u, 0x115Fu, 0xA960u, 0xA97Cu))
#define isV(u) (hb_in_ranges<hb_codepoint_t> ((u), 0x1160u, 0x11A7u, 0xD7B0u, 0xD7C6u))
#define isT(u) (hb_in_ranges<hb_codepoint_t> ((u), 0x11A8u, 0x11FFu, 0xD7CBu, 0xD7FBu))

#define isHangulTone(u) (hb_in_range<hb_codepoint_t> ((u), 0x302Eu, 0x302Fu))

/* buffer var allocations */
#define hangul_shaping_feature() complex_var_u8_0() /* hangul jamo shaping feature */

static bool
is_zero_width_char (hb_font_t *font,
		    hb_codepoint_t unicode)
{
  hb_codepoint_t glyph;
  return hb_font_get_glyph (font, unicode, 0, &glyph) && hb_font_get_glyph_h_advance (font, glyph) == 0;
}

static void
preprocess_text_hangul (const hb_ot_shape_plan_t *plan HB_UNUSED,
			hb_buffer_t              *buffer,
			hb_font_t                *font)
{
  HB_BUFFER_ALLOCATE_VAR (buffer, hangul_shaping_feature);

  /* Hangul syllables come in two shapes: LV, and LVT.  Of those:
   *
   *   - LV can be precomposed, or decomposed.  Lets call those
   *     <LV> and <L,V>,
   *   - LVT can be fully precomposed, partically precomposed, or
   *     fully decomposed.  Ie. <LVT>, <LV,T>, or <L,V,T>.
   *
   * The composition / decomposition is mechanical.  However, not
   * all <L,V> sequences compose, and not all <LV,T> sequences
   * compose.
   *
   * Here are the specifics:
   *
   *   - <L>: U+1100..115F, U+A960..A97F
   *   - <V>: U+1160..11A7, U+D7B0..D7C7
   *   - <T>: U+11A8..11FF, U+D7CB..D7FB
   *
   *   - Only the <L,V> sequences for some of the U+11xx ranges combine.
   *   - Only <LV,T> sequences for some of the Ts in U+11xx range combine.
   *
   * Here is what we want to accomplish in this shaper:
   *
   *   - If the whole syllable can be precomposed, do that,
   *   - Otherwise, fully decompose and apply ljmo/vjmo/tjmo features.
   *   - If a valid syllable is followed by a Hangul tone mark, reorder the tone
   *     mark to precede the whole syllable - unless it is a zero-width glyph, in
   *     which case we leave it untouched, assuming it's designed to overstrike.
   *
   * That is, of the different possible syllables:
   *
   *   <L>
   *   <L,V>
   *   <L,V,T>
   *   <LV>
   *   <LVT>
   *   <LV, T>
   *
   * - <L> needs no work.
   *
   * - <LV> and <LVT> can stay the way they are if the font supports them, otherwise we
   *   should fully decompose them if font supports.
   *
   * - <L,V> and <L,V,T> we should compose if the whole thing can be composed.
   *
   * - <LV,T> we should compose if the whole thing can be composed, otherwise we should
   *   decompose.
   */

  buffer->clear_output ();
  unsigned int start = 0, end = 0; /* Extent of most recently seen syllable;
				    * valid only if start < end
				    */
  unsigned int count = buffer->len;

  for (buffer->idx = 0; buffer->idx < count && buffer->successful;)
  {
    hb_codepoint_t u = buffer->cur().codepoint;

    if (isHangulTone (u))
    {
      /*
       * We could cache the width of the tone marks and the existence of dotted-circle,
       * but the use of the Hangul tone mark characters seems to be rare enough that
       * I didn't bother for now.
       */
      if (start < end && end == buffer->out_len)
      {
	/* Tone mark follows a valid syllable; move it in front, unless it's zero width. */
	buffer->unsafe_to_break_from_outbuffer (start, buffer->idx);
	buffer->next_glyph ();
	if (!is_zero_width_char (font, u))
	{
	  buffer->merge_out_clusters (start, end + 1);
	  hb_glyph_info_t *info = buffer->out_info;
	  hb_glyph_info_t tone = info[end];
	  memmove (&info[start + 1], &info[start], (end - start) * sizeof (hb_glyph_info_t));
	  info[start] = tone;
	}
      }
      else
      {
	/* No valid syllable as base for tone mark; try to insert dotted circle. */
      if (!(buffer->flags & HB_BUFFER_FLAG_DO_NOT_INSERT_DOTTED_CIRCLE) &&
	  font->has_glyph (0x25CCu))
	{
	  hb_codepoint_t chars[2];
	  if (!is_zero_width_char (font, u)) {
	    chars[0] = u;
	    chars[1] = 0x25CCu;
	  } else {
	    chars[0] = 0x25CCu;
	    chars[1] = u;
	  }
	  buffer->replace_glyphs (1, 2, chars);
	}
	else
	{
	  /* No dotted circle available in the font; just leave tone mark untouched. */
	  buffer->next_glyph ();
	}
      }
      start = end = buffer->out_len;
      continue;
    }

    start = buffer->out_len; /* Remember current position as a potential syllable start;
			      * will only be used if we set end to a later position.
			      */

    if (isL (u) && buffer->idx + 1 < count)
    {
      hb_codepoint_t l = u;
      hb_codepoint_t v = buffer->cur(+1).codepoint;
      if (isV (v))
      {
	/* Have <L,V> or <L,V,T>. */
	hb_codepoint_t t = 0;
	unsigned int tindex = 0;
	if (buffer->idx + 2 < count)
	{
	  t = buffer->cur(+2).codepoint;
	  if (isT (t))
	    tindex = t - TBase; /* Only used if isCombiningT (t); otherwise invalid. */
	  else
	    t = 0; /* The next character was not a trailing jamo. */
	}
	buffer->unsafe_to_break (buffer->idx, buffer->idx + (t ? 3 : 2));

	/* We've got a syllable <L,V,T?>; see if it can potentially be composed. */
	if (isCombiningL (l) && isCombiningV (v) && (t == 0 || isCombiningT (t)))
	{
	  /* Try to compose; if this succeeds, end is set to start+1. */
	  hb_codepoint_t s = SBase + (l - LBase) * NCount + (v - VBase) * TCount + tindex;
	  if (font->has_glyph (s))
	  {
	    buffer->replace_glyphs (t ? 3 : 2, 1, &s);
	    if (unlikely (!buffer->successful))
	      return;
	    end = start + 1;
	    continue;
	  }
	}

	/* We didn't compose, either because it's an Old Hangul syllable without a
	 * precomposed character in Unicode, or because the font didn't support the
	 * necessary precomposed glyph.
	 * Set jamo features on the individual glyphs, and advance past them.
	 */
	buffer->cur().hangul_shaping_feature() = LJMO;
	buffer->next_glyph ();
	buffer->cur().hangul_shaping_feature() = VJMO;
	buffer->next_glyph ();
	if (t)
	{
	  buffer->cur().hangul_shaping_feature() = TJMO;
	  buffer->next_glyph ();
	  end = start + 3;
	}
	else
	  end = start + 2;
	if (buffer->cluster_level == HB_BUFFER_CLUSTER_LEVEL_MONOTONE_GRAPHEMES)
	  buffer->merge_out_clusters (start, end);
	continue;
      }
    }

    else if (isCombinedS (u))
    {
      /* Have <LV>, <LVT>, or <LV,T> */
      hb_codepoint_t s = u;
      bool has_glyph = font->has_glyph (s);
      unsigned int lindex = (s - SBase) / NCount;
      unsigned int nindex = (s - SBase) % NCount;
      unsigned int vindex = nindex / TCount;
      unsigned int tindex = nindex % TCount;

      if (!tindex &&
	  buffer->idx + 1 < count &&
	  isCombiningT (buffer->cur(+1).codepoint))
      {
	/* <LV,T>, try to combine. */
	unsigned int new_tindex = buffer->cur(+1).codepoint - TBase;
	hb_codepoint_t new_s = s + new_tindex;
	if (font->has_glyph (new_s))
	{
	  buffer->replace_glyphs (2, 1, &new_s);
	  if (unlikely (!buffer->successful))
	    return;
	  end = start + 1;
	  continue;
	}
	else
	  buffer->unsafe_to_break (buffer->idx, buffer->idx + 2); /* Mark unsafe between LV and T. */
      }

      /* Otherwise, decompose if font doesn't support <LV> or <LVT>,
       * or if having non-combining <LV,T>.  Note that we already handled
       * combining <LV,T> above. */
      if (!has_glyph ||
	  (!tindex &&
	   buffer->idx + 1 < count &&
	   isT (buffer->cur(+1).codepoint)))
      {
	hb_codepoint_t decomposed[3] = {LBase + lindex,
					VBase + vindex,
					TBase + tindex};
	if (font->has_glyph (decomposed[0]) &&
	    font->has_glyph (decomposed[1]) &&
	    (!tindex || font->has_glyph (decomposed[2])))
	{
	  unsigned int s_len = tindex ? 3 : 2;
	  buffer->replace_glyphs (1, s_len, decomposed);

	  /* If we decomposed an LV because of a non-combining T following,
	   * we want to include this T in the syllable.
	   */
	  if (has_glyph && !tindex)
	  {
	    buffer->next_glyph ();
	    s_len++;
	  }

	  if (unlikely (!buffer->successful))
	    return;

	  /* We decomposed S: apply jamo features to the individual glyphs
	   * that are now in buffer->out_info.
	   */
	  hb_glyph_info_t *info = buffer->out_info;
	  end = start + s_len;

	  unsigned int i = start;
	  info[i++].hangul_shaping_feature() = LJMO;
	  info[i++].hangul_shaping_feature() = VJMO;
	  if (i < end)
	    info[i++].hangul_shaping_feature() = TJMO;

	  if (buffer->cluster_level == HB_BUFFER_CLUSTER_LEVEL_MONOTONE_GRAPHEMES)
	    buffer->merge_out_clusters (start, end);
	  continue;
	}
	else if ((!tindex && buffer->idx + 1 < count && isT (buffer->cur(+1).codepoint)))
	  buffer->unsafe_to_break (buffer->idx, buffer->idx + 2); /* Mark unsafe between LV and T. */
      }

      if (has_glyph)
      {
	/* We didn't decompose the S, so just advance past it. */
	end = start + 1;
	buffer->next_glyph ();
	continue;
      }
    }

    /* Didn't find a recognizable syllable, so we leave end <= start;
     * this will prevent tone-mark reordering happening.
     */
    buffer->next_glyph ();
  }
  buffer->swap_buffers ();
}

static void
setup_masks_hangul (const hb_ot_shape_plan_t *plan,
		    hb_buffer_t              *buffer,
		    hb_font_t                *font HB_UNUSED)
{
  const hangul_shape_plan_t *hangul_plan = (const hangul_shape_plan_t *) plan->data;

  if (likely (hangul_plan))
  {
    unsigned int count = buffer->len;
    hb_glyph_info_t *info = buffer->info;
    for (unsigned int i = 0; i < count; i++, info++)
      info->mask |= hangul_plan->mask_array[info->hangul_shaping_feature()];
  }

  HB_BUFFER_DEALLOCATE_VAR (buffer, hangul_shaping_feature);
}

const hb_ot_complex_shaper_t _hb_ot_complex_shaper_hangul =
{
  collect_features_hangul,
  override_features_hangul,
  data_create_hangul,
  data_destroy_hangul,
  preprocess_text_hangul,
  nullptr, /* postprocess_glyphs */
  HB_OT_SHAPE_NORMALIZATION_MODE_NONE,
  nullptr, /* decompose */
  nullptr, /* compose */
  setup_masks_hangul,
  HB_TAG_NONE, /* gpos_tag */
  nullptr, /* reorder_marks */
  HB_OT_SHAPE_ZERO_WIDTH_MARKS_NONE,
  false, /* fallback_position */
};

#endif


text:
/*
 * Copyright © 2015-2019  Ebrahim Byagowi
 *
 *  This is part of HarfBuzz, a text shaping library.
 *
 * Permission is hereby granted, without written agreement and without
 * license or royalty fees, to use, copy, modify, and distribute this
 * software and its documentation for any purpose, provided that the
 * above copyright notice and the following two paragraphs appear in
 * all copies of this software.
 *
 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
 * DAMAGE.
 *
 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
 * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
 */

#include "hb.hh"

#ifdef HAVE_DIRECTWRITE

#include "hb-shaper-impl.hh"

#include <dwrite_1.h>

#include "hb-directwrite.h"

/* Declare object creator for dynamic support of DWRITE */
typedef HRESULT (* WINAPI t_DWriteCreateFactory)(
  DWRITE_FACTORY_TYPE factoryType,
  REFIID              iid,
  IUnknown            **factory
);

/*
 * hb-directwrite uses new/delete syntatically but as we let users
 * to override malloc/free, we will redefine new/delete so users
 * won't need to do that by their own.
 */
void* operator new (size_t size)        { return malloc (size); }
void* operator new [] (size_t size)     { return malloc (size); }
void operator delete (void* pointer)    { free (pointer); }
void operator delete [] (void* pointer) { free (pointer); }

/*
 * DirectWrite font stream helpers
 */

// This is a font loader which provides only one font (unlike its original design).
// For a better implementation which was also source of this
// and DWriteFontFileStream, have a look at to NativeFontResourceDWrite.cpp in Mozilla
class DWriteFontFileLoader : public IDWriteFontFileLoader
{
private:
  IDWriteFontFileStream *mFontFileStream;
public:
  DWriteFontFileLoader (IDWriteFontFileStream *fontFileStream)
  { mFontFileStream = fontFileStream; }

  // IUnknown interface
  IFACEMETHOD (QueryInterface) (IID const& iid, OUT void** ppObject)
  { return S_OK; }
  IFACEMETHOD_ (ULONG, AddRef) ()  { return 1; }
  IFACEMETHOD_ (ULONG, Release) () { return 1; }

  // IDWriteFontFileLoader methods
  virtual HRESULT STDMETHODCALLTYPE
  CreateStreamFromKey (void const* fontFileReferenceKey,
		       uint32_t fontFileReferenceKeySize,
		       OUT IDWriteFontFileStream** fontFileStream)
  {
    *fontFileStream = mFontFileStream;
    return S_OK;
  }

  virtual ~DWriteFontFileLoader() {}
};

class DWriteFontFileStream : public IDWriteFontFileStream
{
private:
  uint8_t *mData;
  uint32_t mSize;
public:
  DWriteFontFileStream (uint8_t *aData, uint32_t aSize)
  {
    mData = aData;
    mSize = aSize;
  }

  // IUnknown interface
  IFACEMETHOD (QueryInterface) (IID const& iid, OUT void** ppObject)
  { return S_OK; }
  IFACEMETHOD_ (ULONG, AddRef) ()  { return 1; }
  IFACEMETHOD_ (ULONG, Release) () { return 1; }

  // IDWriteFontFileStream methods
  virtual HRESULT STDMETHODCALLTYPE
  ReadFileFragment (void const** fragmentStart,
		    UINT64 fileOffset,
		    UINT64 fragmentSize,
		    OUT void** fragmentContext)
  {
    // We are required to do bounds checking.
    if (fileOffset + fragmentSize > mSize) return E_FAIL;

    // truncate the 64 bit fileOffset to size_t sized index into mData
    size_t index = static_cast<size_t> (fileOffset);

    // We should be alive for the duration of this.
    *fragmentStart = &mData[index];
    *fragmentContext = nullptr;
    return S_OK;
  }

  virtual void STDMETHODCALLTYPE
  ReleaseFileFragment (void* fragmentContext) {}

  virtual HRESULT STDMETHODCALLTYPE
  GetFileSize (OUT UINT64* fileSize)
  {
    *fileSize = mSize;
    return S_OK;
  }

  virtual HRESULT STDMETHODCALLTYPE
  GetLastWriteTime (OUT UINT64* lastWriteTime) { return E_NOTIMPL; }

  virtual ~DWriteFontFileStream() {}
};

/*
* shaper face data
*/

struct hb_directwrite_face_data_t
{
  HMODULE dwrite_dll;
  IDWriteFactory *dwriteFactory;
  IDWriteFontFile *fontFile;
  DWriteFontFileStream *fontFileStream;
  DWriteFontFileLoader *fontFileLoader;
  IDWriteFontFace *fontFace;
  hb_blob_t *faceBlob;
};

hb_directwrite_face_data_t *
_hb_directwrite_shaper_face_data_create (hb_face_t *face)
{
  hb_directwrite_face_data_t *data = new hb_directwrite_face_data_t;
  if (unlikely (!data))
    return nullptr;

#define FAIL(...) \
  HB_STMT_START { \
    DEBUG_MSG (DIRECTWRITE, nullptr, __VA_ARGS__); \
    return nullptr; \
  } HB_STMT_END

  data->dwrite_dll = LoadLibrary (TEXT ("DWRITE"));
  if (unlikely (!data->dwrite_dll))
    FAIL ("Cannot find DWrite.DLL");

  t_DWriteCreateFactory p_DWriteCreateFactory;

#if defined(__GNUC__)
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wcast-function-type"
#endif

  p_DWriteCreateFactory = (t_DWriteCreateFactory)
			  GetProcAddress (data->dwrite_dll, "DWriteCreateFactory");

#if defined(__GNUC__)
#pragma GCC diagnostic pop
#endif

  if (unlikely (!p_DWriteCreateFactory))
    FAIL ("Cannot find DWriteCreateFactory().");

  HRESULT hr;

  // TODO: factory and fontFileLoader should be cached separately
  IDWriteFactory* dwriteFactory;
  hr = p_DWriteCreateFactory (DWRITE_FACTORY_TYPE_SHARED, __uuidof (IDWriteFactory),
			      (IUnknown**) &dwriteFactory);

  if (unlikely (hr != S_OK))
    FAIL ("Failed to run DWriteCreateFactory().");

  hb_blob_t *blob = hb_face_reference_blob (face);
  DWriteFontFileStream *fontFileStream;
  fontFileStream = new DWriteFontFileStream ((uint8_t *) hb_blob_get_data (blob, nullptr),
					     hb_blob_get_length (blob));

  DWriteFontFileLoader *fontFileLoader = new DWriteFontFileLoader (fontFileStream);
  dwriteFactory->RegisterFontFileLoader (fontFileLoader);

  IDWriteFontFile *fontFile;
  uint64_t fontFileKey = 0;
  hr = dwriteFactory->CreateCustomFontFileReference (&fontFileKey, sizeof (fontFileKey),
						     fontFileLoader, &fontFile);

  if (FAILED (hr))
    FAIL ("Failed to load font file from data!");

  BOOL isSupported;
  DWRITE_FONT_FILE_TYPE fileType;
  DWRITE_FONT_FACE_TYPE faceType;
  uint32_t numberOfFaces;
  hr = fontFile->Analyze (&isSupported, &fileType, &faceType, &numberOfFaces);
  if (FAILED (hr) || !isSupported)
    FAIL ("Font file is not supported.");

#undef FAIL

  IDWriteFontFace *fontFace;
  dwriteFactory->CreateFontFace (faceType, 1, &fontFile, 0,
				 DWRITE_FONT_SIMULATIONS_NONE, &fontFace);

  data->dwriteFactory = dwriteFactory;
  data->fontFile = fontFile;
  data->fontFileStream = fontFileStream;
  data->fontFileLoader = fontFileLoader;
  data->fontFace = fontFace;
  data->faceBlob = blob;

  return data;
}

void
_hb_directwrite_shaper_face_data_destroy (hb_directwrite_face_data_t *data)
{
  if (data->fontFace)
    data->fontFace->Release ();
  if (data->fontFile)
    data->fontFile->Release ();
  if (data->dwriteFactory)
  {
    if (data->fontFileLoader)
      data->dwriteFactory->UnregisterFontFileLoader (data->fontFileLoader);
    data->dwriteFactory->Release ();
  }
  if (data->fontFileLoader)
    delete data->fontFileLoader;
  if (data->fontFileStream)
    delete data->fontFileStream;
  if (data->faceBlob)
    hb_blob_destroy (data->faceBlob);
  if (data->dwrite_dll)
    FreeLibrary (data->dwrite_dll);
  if (data)
    delete data;
}

/*
 * shaper font data
 */

struct hb_directwrite_font_data_t {};

hb_directwrite_font_data_t *
_hb_directwrite_shaper_font_data_create (hb_font_t *font)
{
  hb_directwrite_font_data_t *data = new hb_directwrite_font_data_t;
  if (unlikely (!data))
    return nullptr;

  return data;
}

void
_hb_directwrite_shaper_font_data_destroy (hb_directwrite_font_data_t *data)
{
  delete data;
}

// Most of TextAnalysis is originally written by Bas Schouten for Mozilla project
// but now is relicensed to MIT for HarfBuzz use
class TextAnalysis : public IDWriteTextAnalysisSource, public IDWriteTextAnalysisSink
{
public:

  IFACEMETHOD (QueryInterface) (IID const& iid, OUT void** ppObject)
  { return S_OK; }
  IFACEMETHOD_ (ULONG, AddRef) () { return 1; }
  IFACEMETHOD_ (ULONG, Release) () { return 1; }

  // A single contiguous run of characters containing the same analysis
  // results.
  struct Run
  {
    uint32_t mTextStart;   // starting text position of this run
    uint32_t mTextLength;  // number of contiguous code units covered
    uint32_t mGlyphStart;  // starting glyph in the glyphs array
    uint32_t mGlyphCount;  // number of glyphs associated with this run
    // text
    DWRITE_SCRIPT_ANALYSIS mScript;
    uint8_t mBidiLevel;
    bool mIsSideways;

    bool ContainsTextPosition (uint32_t aTextPosition) const
    {
      return aTextPosition >= mTextStart &&
	     aTextPosition <  mTextStart + mTextLength;
    }

    Run *nextRun;
  };

public:
  TextAnalysis (const wchar_t* text, uint32_t textLength,
		const wchar_t* localeName, DWRITE_READING_DIRECTION readingDirection)
	       : mTextLength (textLength), mText (text), mLocaleName (localeName),
		 mReadingDirection (readingDirection), mCurrentRun (nullptr) {}
  ~TextAnalysis ()
  {
    // delete runs, except mRunHead which is part of the TextAnalysis object
    for (Run *run = mRunHead.nextRun; run;)
    {
      Run *origRun = run;
      run = run->nextRun;
      delete origRun;
    }
  }

  STDMETHODIMP
  GenerateResults (IDWriteTextAnalyzer* textAnalyzer, Run **runHead)
  {
    // Analyzes the text using the script analyzer and returns
    // the result as a series of runs.

    HRESULT hr = S_OK;

    // Initially start out with one result that covers the entire range.
    // This result will be subdivided by the analysis processes.
    mRunHead.mTextStart = 0;
    mRunHead.mTextLength = mTextLength;
    mRunHead.mBidiLevel =
      (mReadingDirection == DWRITE_READING_DIRECTION_RIGHT_TO_LEFT);
    mRunHead.nextRun = nullptr;
    mCurrentRun = &mRunHead;

    // Call each of the analyzers in sequence, recording their results.
    if (SUCCEEDED (hr = textAnalyzer->AnalyzeScript (this, 0, mTextLength, this)))
      *runHead = &mRunHead;

    return hr;
  }

  // IDWriteTextAnalysisSource implementation

  IFACEMETHODIMP
  GetTextAtPosition (uint32_t textPosition,
		     OUT wchar_t const** textString,
		     OUT uint32_t* textLength)
  {
    if (textPosition >= mTextLength)
    {
      // No text at this position, valid query though.
      *textString = nullptr;
      *textLength = 0;
    }
    else
    {
      *textString = mText + textPosition;
      *textLength = mTextLength - textPosition;
    }
    return S_OK;
  }

  IFACEMETHODIMP
  GetTextBeforePosition (uint32_t textPosition,
			 OUT wchar_t const** textString,
			 OUT uint32_t* textLength)
  {
    if (textPosition == 0 || textPosition > mTextLength)
    {
      // Either there is no text before here (== 0), or this
      // is an invalid position. The query is considered valid though.
      *textString = nullptr;
      *textLength = 0;
    }
    else
    {
      *textString = mText;
      *textLength = textPosition;
    }
    return S_OK;
  }

  IFACEMETHODIMP_ (DWRITE_READING_DIRECTION)
  GetParagraphReadingDirection () { return mReadingDirection; }

  IFACEMETHODIMP GetLocaleName (uint32_t textPosition, uint32_t* textLength,
				wchar_t const** localeName)
  { return S_OK; }

  IFACEMETHODIMP
  GetNumberSubstitution (uint32_t textPosition,
			 OUT uint32_t* textLength,
			 OUT IDWriteNumberSubstitution** numberSubstitution)
  {
    // We do not support number substitution.
    *numberSubstitution = nullptr;
    *textLength = mTextLength - textPosition;

    return S_OK;
  }

  // IDWriteTextAnalysisSink implementation

  IFACEMETHODIMP
  SetScriptAnalysis (uint32_t textPosition, uint32_t textLength,
		     DWRITE_SCRIPT_ANALYSIS const* scriptAnalysis)
  {
    SetCurrentRun (textPosition);
    SplitCurrentRun (textPosition);
    while (textLength > 0)
    {
      Run *run = FetchNextRun (&textLength);
      run->mScript = *scriptAnalysis;
    }

    return S_OK;
  }

  IFACEMETHODIMP
  SetLineBreakpoints (uint32_t textPosition,
		      uint32_t textLength,
		      const DWRITE_LINE_BREAKPOINT* lineBreakpoints)
  { return S_OK; }

  IFACEMETHODIMP SetBidiLevel (uint32_t textPosition, uint32_t textLength,
			       uint8_t explicitLevel, uint8_t resolvedLevel)
  { return S_OK; }

  IFACEMETHODIMP
  SetNumberSubstitution (uint32_t textPosition, uint32_t textLength,
			 IDWriteNumberSubstitution* numberSubstitution)
  { return S_OK; }

protected:
  Run *FetchNextRun (IN OUT uint32_t* textLength)
  {
    // Used by the sink setters, this returns a reference to the next run.
    // Position and length are adjusted to now point after the current run
    // being returned.

    Run *origRun = mCurrentRun;
    // Split the tail if needed (the length remaining is less than the
    // current run's size).
    if (*textLength < mCurrentRun->mTextLength)
      SplitCurrentRun (mCurrentRun->mTextStart + *textLength);
    else
      // Just advance the current run.
      mCurrentRun = mCurrentRun->nextRun;
    *textLength -= origRun->mTextLength;

    // Return a reference to the run that was just current.
    return origRun;
  }

  void SetCurrentRun (uint32_t textPosition)
  {
    // Move the current run to the given position.
    // Since the analyzers generally return results in a forward manner,
    // this will usually just return early. If not, find the
    // corresponding run for the text position.

    if (mCurrentRun && mCurrentRun->ContainsTextPosition (textPosition))
      return;

    for (Run *run = &mRunHead; run; run = run->nextRun)
      if (run->ContainsTextPosition (textPosition))
      {
	mCurrentRun = run;
	return;
      }
    assert (0); // We should always be able to find the text position in one of our runs
  }

  void SplitCurrentRun (uint32_t splitPosition)
  {
    if (!mCurrentRun)
    {
      assert (0); // SplitCurrentRun called without current run
      // Shouldn't be calling this when no current run is set!
      return;
    }
    // Split the current run.
    if (splitPosition <= mCurrentRun->mTextStart)
    {
      // No need to split, already the start of a run
      // or before it. Usually the first.
      return;
    }
    Run *newRun = new Run;

    *newRun = *mCurrentRun;

    // Insert the new run in our linked list.
    newRun->nextRun = mCurrentRun->nextRun;
    mCurrentRun->nextRun = newRun;

    // Adjust runs' text positions and lengths.
    uint32_t splitPoint = splitPosition - mCurrentRun->mTextStart;
    newRun->mTextStart += splitPoint;
    newRun->mTextLength -= splitPoint;
    mCurrentRun->mTextLength = splitPoint;
    mCurrentRun = newRun;
  }

protected:
  // Input
  // (weak references are fine here, since this class is a transient
  //  stack-based helper that doesn't need to copy data)
  uint32_t mTextLength;
  const wchar_t* mText;
  const wchar_t* mLocaleName;
  DWRITE_READING_DIRECTION mReadingDirection;

  // Current processing state.
  Run *mCurrentRun;

  // Output is a list of runs starting here
  Run  mRunHead;
};

/*
 * shaper
 */

static hb_bool_t
_hb_directwrite_shape_full (hb_shape_plan_t    *shape_plan,
			    hb_font_t          *font,
			    hb_buffer_t        *buffer,
			    const hb_feature_t *features,
			    unsigned int        num_features,
			    float               lineWidth)
{
  hb_face_t *face = font->face;
  const hb_directwrite_face_data_t *face_data = face->data.directwrite;
  IDWriteFactory *dwriteFactory = face_data->dwriteFactory;
  IDWriteFontFace *fontFace = face_data->fontFace;

  IDWriteTextAnalyzer* analyzer;
  dwriteFactory->CreateTextAnalyzer (&analyzer);

  unsigned int scratch_size;
  hb_buffer_t::scratch_buffer_t *scratch = buffer->get_scratch_buffer (&scratch_size);
#define ALLOCATE_ARRAY(Type, name, len) \
  Type *name = (Type *) scratch; \
  do { \
    unsigned int _consumed = DIV_CEIL ((len) * sizeof (Type), sizeof (*scratch)); \
    assert (_consumed <= scratch_size); \
    scratch += _consumed; \
    scratch_size -= _consumed; \
  } while (0)

#define utf16_index() var1.u32

  ALLOCATE_ARRAY (wchar_t, textString, buffer->len * 2);

  unsigned int chars_len = 0;
  for (unsigned int i = 0; i < buffer->len; i++)
  {
    hb_codepoint_t c = buffer->info[i].codepoint;
    buffer->info[i].utf16_index () = chars_len;
    if (likely (c <= 0xFFFFu))
      textString[chars_len++] = c;
    else if (unlikely (c > 0x10FFFFu))
      textString[chars_len++] = 0xFFFDu;
    else
    {
      textString[chars_len++] = 0xD800u + ((c - 0x10000u) >> 10);
      textString[chars_len++] = 0xDC00u + ((c - 0x10000u) & ((1u << 10) - 1));
    }
  }

  ALLOCATE_ARRAY (WORD, log_clusters, chars_len);
  /* Need log_clusters to assign features. */
  chars_len = 0;
  for (unsigned int i = 0; i < buffer->len; i++)
  {
    hb_codepoint_t c = buffer->info[i].codepoint;
    unsigned int cluster = buffer->info[i].cluster;
    log_clusters[chars_len++] = cluster;
    if (hb_in_range (c, 0x10000u, 0x10FFFFu))
      log_clusters[chars_len++] = cluster; /* Surrogates. */
  }

  // TODO: Handle TEST_DISABLE_OPTIONAL_LIGATURES

  DWRITE_READING_DIRECTION readingDirection;
  readingDirection = buffer->props.direction ?
		     DWRITE_READING_DIRECTION_RIGHT_TO_LEFT :
		     DWRITE_READING_DIRECTION_LEFT_TO_RIGHT;

  /*
  * There's an internal 16-bit limit on some things inside the analyzer,
  * but we never attempt to shape a word longer than 64K characters
  * in a single gfxShapedWord, so we cannot exceed that limit.
  */
  uint32_t textLength = buffer->len;

  TextAnalysis analysis (textString, textLength, nullptr, readingDirection);
  TextAnalysis::Run *runHead;
  HRESULT hr;
  hr = analysis.GenerateResults (analyzer, &runHead);

#define FAIL(...) \
  HB_STMT_START { \
    DEBUG_MSG (DIRECTWRITE, nullptr, __VA_ARGS__); \
    return false; \
  } HB_STMT_END

  if (FAILED (hr))
    FAIL ("Analyzer failed to generate results.");

  uint32_t maxGlyphCount = 3 * textLength / 2 + 16;
  uint32_t glyphCount;
  bool isRightToLeft = HB_DIRECTION_IS_BACKWARD (buffer->props.direction);

  const wchar_t localeName[20] = {0};
  if (buffer->props.language)
    mbstowcs ((wchar_t*) localeName,
	      hb_language_to_string (buffer->props.language), 20);

  // TODO: it does work but doesn't care about ranges
  DWRITE_TYPOGRAPHIC_FEATURES typographic_features;
  typographic_features.featureCount = num_features;
  if (num_features)
  {
    typographic_features.features = new DWRITE_FONT_FEATURE[num_features];
    for (unsigned int i = 0; i < num_features; ++i)
    {
      typographic_features.features[i].nameTag = (DWRITE_FONT_FEATURE_TAG)
						 hb_uint32_swap (features[i].tag);
      typographic_features.features[i].parameter = features[i].value;
    }
  }
  const DWRITE_TYPOGRAPHIC_FEATURES* dwFeatures;
  dwFeatures = (const DWRITE_TYPOGRAPHIC_FEATURES*) &typographic_features;
  const uint32_t featureRangeLengths[] = { textLength };
  //

  uint16_t* clusterMap;
  clusterMap = new uint16_t[textLength];
  DWRITE_SHAPING_TEXT_PROPERTIES* textProperties;
  textProperties = new DWRITE_SHAPING_TEXT_PROPERTIES[textLength];
retry_getglyphs:
  uint16_t* glyphIndices = new uint16_t[maxGlyphCount];
  DWRITE_SHAPING_GLYPH_PROPERTIES* glyphProperties;
  glyphProperties = new DWRITE_SHAPING_GLYPH_PROPERTIES[maxGlyphCount];

  hr = analyzer->GetGlyphs (textString, textLength, fontFace, false,
			    isRightToLeft, &runHead->mScript, localeName,
			    nullptr, &dwFeatures, featureRangeLengths, 1,
			    maxGlyphCount, clusterMap, textProperties,
			    glyphIndices, glyphProperties, &glyphCount);

  if (unlikely (hr == HRESULT_FROM_WIN32 (ERROR_INSUFFICIENT_BUFFER)))
  {
    delete [] glyphIndices;
    delete [] glyphProperties;

    maxGlyphCount *= 2;

    goto retry_getglyphs;
  }
  if (FAILED (hr))
    FAIL ("Analyzer failed to get glyphs.");

  float* glyphAdvances = new float[maxGlyphCount];
  DWRITE_GLYPH_OFFSET* glyphOffsets = new DWRITE_GLYPH_OFFSET[maxGlyphCount];

  /* The -2 in the following is to compensate for possible
   * alignment needed after the WORD array.  sizeof (WORD) == 2. */
  unsigned int glyphs_size = (scratch_size * sizeof (int) - 2)
			     / (sizeof (WORD) +
				sizeof (DWRITE_SHAPING_GLYPH_PROPERTIES) +
				sizeof (int) +
				sizeof (DWRITE_GLYPH_OFFSET) +
				sizeof (uint32_t));
  ALLOCATE_ARRAY (uint32_t, vis_clusters, glyphs_size);

#undef ALLOCATE_ARRAY

  int fontEmSize = font->face->get_upem ();
  if (fontEmSize < 0) fontEmSize = -fontEmSize;

  if (fontEmSize < 0) fontEmSize = -fontEmSize;
  double x_mult = (double) font->x_scale / fontEmSize;
  double y_mult = (double) font->y_scale / fontEmSize;

  hr = analyzer->GetGlyphPlacements (textString, clusterMap, textProperties,
				     textLength, glyphIndices, glyphProperties,
				     glyphCount, fontFace, fontEmSize,
				     false, isRightToLeft, &runHead->mScript, localeName,
				     &dwFeatures, featureRangeLengths, 1,
				     glyphAdvances, glyphOffsets);

  if (FAILED (hr))
    FAIL ("Analyzer failed to get glyph placements.");

  IDWriteTextAnalyzer1* analyzer1;
  analyzer->QueryInterface (&analyzer1);

  if (analyzer1 && lineWidth)
  {
    DWRITE_JUSTIFICATION_OPPORTUNITY* justificationOpportunities =
      new DWRITE_JUSTIFICATION_OPPORTUNITY[maxGlyphCount];
    hr = analyzer1->GetJustificationOpportunities (fontFace, fontEmSize, runHead->mScript,
						   textLength, glyphCount, textString,
						   clusterMap, glyphProperties,
						   justificationOpportunities);

    if (FAILED (hr))
      FAIL ("Analyzer failed to get justification opportunities.");

    float* justifiedGlyphAdvances = new float[maxGlyphCount];
    DWRITE_GLYPH_OFFSET* justifiedGlyphOffsets = new DWRITE_GLYPH_OFFSET[glyphCount];
    hr = analyzer1->JustifyGlyphAdvances (lineWidth, glyphCount, justificationOpportunities,
					  glyphAdvances, glyphOffsets, justifiedGlyphAdvances,
					  justifiedGlyphOffsets);

    if (FAILED (hr)) FAIL ("Analyzer failed to get justify glyph advances.");

    DWRITE_SCRIPT_PROPERTIES scriptProperties;
    hr = analyzer1->GetScriptProperties (runHead->mScript, &scriptProperties);
    if (FAILED (hr)) FAIL ("Analyzer failed to get script properties.");
    uint32_t justificationCharacter = scriptProperties.justificationCharacter;

    // if a script justificationCharacter is not space, it can have GetJustifiedGlyphs
    if (justificationCharacter != 32)
    {
      uint16_t* modifiedClusterMap = new uint16_t[textLength];
    retry_getjustifiedglyphs:
      uint16_t* modifiedGlyphIndices = new uint16_t[maxGlyphCount];
      float* modifiedGlyphAdvances = new float[maxGlyphCount];
      DWRITE_GLYPH_OFFSET* modifiedGlyphOffsets = new DWRITE_GLYPH_OFFSET[maxGlyphCount];
      uint32_t actualGlyphsCount;
      hr = analyzer1->GetJustifiedGlyphs (fontFace, fontEmSize, runHead->mScript,
					  textLength, glyphCount, maxGlyphCount,
					  clusterMap, glyphIndices, glyphAdvances,
					  justifiedGlyphAdvances, justifiedGlyphOffsets,
					  glyphProperties, &actualGlyphsCount,
					  modifiedClusterMap, modifiedGlyphIndices,
					  modifiedGlyphAdvances, modifiedGlyphOffsets);

      if (hr == HRESULT_FROM_WIN32 (ERROR_INSUFFICIENT_BUFFER))
      {
	maxGlyphCount = actualGlyphsCount;
	delete [] modifiedGlyphIndices;
	delete [] modifiedGlyphAdvances;
	delete [] modifiedGlyphOffsets;

	maxGlyphCount = actualGlyphsCount;

	goto retry_getjustifiedglyphs;
      }
      if (FAILED (hr))
	FAIL ("Analyzer failed to get justified glyphs.");

      delete [] clusterMap;
      delete [] glyphIndices;
      delete [] glyphAdvances;
      delete [] glyphOffsets;

      glyphCount = actualGlyphsCount;
      clusterMap = modifiedClusterMap;
      glyphIndices = modifiedGlyphIndices;
      glyphAdvances = modifiedGlyphAdvances;
      glyphOffsets = modifiedGlyphOffsets;

      delete [] justifiedGlyphAdvances;
      delete [] justifiedGlyphOffsets;
    }
    else
    {
      delete [] glyphAdvances;
      delete [] glyphOffsets;

      glyphAdvances = justifiedGlyphAdvances;
      glyphOffsets = justifiedGlyphOffsets;
    }

    delete [] justificationOpportunities;
  }

  /* Ok, we've got everything we need, now compose output buffer,
   * very, *very*, carefully! */

  /* Calculate visual-clusters.  That's what we ship. */
  for (unsigned int i = 0; i < glyphCount; i++)
    vis_clusters[i] = (uint32_t) -1;
  for (unsigned int i = 0; i < buffer->len; i++)
  {
    uint32_t *p =
      &vis_clusters[log_clusters[buffer->info[i].utf16_index ()]];
    *p = hb_min (*p, buffer->info[i].cluster);
  }
  for (unsigned int i = 1; i < glyphCount; i++)
    if (vis_clusters[i] == (uint32_t) -1)
      vis_clusters[i] = vis_clusters[i - 1];

#undef utf16_index

  if (unlikely (!buffer->ensure (glyphCount)))
    FAIL ("Buffer in error");

#undef FAIL

  /* Set glyph infos */
  buffer->len = 0;
  for (unsigned int i = 0; i < glyphCount; i++)
  {
    hb_glyph_info_t *info = &buffer->info[buffer->len++];

    info->codepoint = glyphIndices[i];
    info->cluster = vis_clusters[i];

    /* The rest is crap.  Let's store position info there for now. */
    info->mask = glyphAdvances[i];
    info->var1.i32 = glyphOffsets[i].advanceOffset;
    info->var2.i32 = glyphOffsets[i].ascenderOffset;
  }

  /* Set glyph positions */
  buffer->clear_positions ();
  for (unsigned int i = 0; i < glyphCount; i++)
  {
    hb_glyph_info_t *info = &buffer->info[i];
    hb_glyph_position_t *pos = &buffer->pos[i];

    /* TODO vertical */
    pos->x_advance = x_mult * (int32_t) info->mask;
    pos->x_offset = x_mult * (isRightToLeft ? -info->var1.i32 : info->var1.i32);
    pos->y_offset = y_mult * info->var2.i32;
  }

  if (isRightToLeft) hb_buffer_reverse (buffer);

  delete [] clusterMap;
  delete [] glyphIndices;
  delete [] textProperties;
  delete [] glyphProperties;
  delete [] glyphAdvances;
  delete [] glyphOffsets;

  if (num_features)
    delete [] typographic_features.features;

  /* Wow, done! */
  return true;
}

hb_bool_t
_hb_directwrite_shape (hb_shape_plan_t    *shape_plan,
		       hb_font_t          *font,
		       hb_buffer_t        *buffer,
		       const hb_feature_t *features,
		       unsigned int        num_features)
{
  return _hb_directwrite_shape_full (shape_plan, font, buffer,
				     features, num_features, 0);
}

HB_UNUSED static bool
_hb_directwrite_shape_experimental_width (hb_font_t          *font,
					  hb_buffer_t        *buffer,
					  const hb_feature_t *features,
					  unsigned int        num_features,
					  float               width)
{
  static const char *shapers = "directwrite";
  hb_shape_plan_t *shape_plan;
  shape_plan = hb_shape_plan_create_cached (font->face, &buffer->props,
					    features, num_features, &shapers);
  hb_bool_t res = _hb_directwrite_shape_full (shape_plan, font, buffer,
					      features, num_features, width);

  buffer->unsafe_to_break_all ();

  return res;
}

struct _hb_directwrite_font_table_context {
  IDWriteFontFace *face;
  void *table_context;
};

static void
_hb_directwrite_table_data_release (void *data)
{
  _hb_directwrite_font_table_context *context = (_hb_directwrite_font_table_context *) data;
  context->face->ReleaseFontTable (context->table_context);
  delete context;
}

static hb_blob_t *
_hb_directwrite_reference_table (hb_face_t *face HB_UNUSED, hb_tag_t tag, void *user_data)
{
  IDWriteFontFace *dw_face = ((IDWriteFontFace *) user_data);
  const void *data;
  uint32_t length;
  void *table_context;
  BOOL exists;
  if (!dw_face || FAILED (dw_face->TryGetFontTable (hb_uint32_swap (tag), &data,
						    &length, &table_context, &exists)))
    return nullptr;

  if (!data || !exists || !length)
  {
    dw_face->ReleaseFontTable (table_context);
    return nullptr;
  }

  _hb_directwrite_font_table_context *context = new _hb_directwrite_font_table_context;
  context->face = dw_face;
  context->table_context = table_context;

  return hb_blob_create ((const char *) data, length, HB_MEMORY_MODE_READONLY,
			 context, _hb_directwrite_table_data_release);
}

static void
_hb_directwrite_font_release (void *data)
{
  if (data)
    ((IDWriteFontFace *) data)->Release ();
}

/**
 * hb_directwrite_face_create:
 * @font_face: a DirectWrite IDWriteFontFace object.
 *
 * Return value: #hb_face_t object corresponding to the given input
 *
 * Since: 2.4.0
 **/
hb_face_t *
hb_directwrite_face_create (IDWriteFontFace *font_face)
{
  if (font_face)
    font_face->AddRef ();
  return hb_face_create_for_tables (_hb_directwrite_reference_table, font_face,
				    _hb_directwrite_font_release);
}

/**
* hb_directwrite_face_get_font_face:
* @face: a #hb_face_t object
*
* Return value: DirectWrite IDWriteFontFace object corresponding to the given input
*
* Since: 2.5.0
**/
IDWriteFontFace *
hb_directwrite_face_get_font_face (hb_face_t *face)
{
  return face->data.directwrite->fontFace;
}

#endif

repo_language: C

mime_type: text/x-c


text:
/*
 * Copyright © 2018  Google, Inc.
 * Copyright © 2019  Facebook, Inc.
 *
 *  This is part of HarfBuzz, a text shaping library.
 *
 * Permission is hereby granted, without written agreement and without
 * license or royalty fees, to use, copy, modify, and distribute this
 * software and its documentation for any purpose, provided that the
 * above copyright notice and the following two paragraphs appear in
 * all copies of this software.
 *
 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
 * DAMAGE.
 *
 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
 * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
 *
 * Google Author(s): Behdad Esfahbod
 * Facebook Author(s): Behdad Esfahbod
 */

#ifndef HB_ITER_HH
#define HB_ITER_HH

#include "hb.hh"
#include "hb-algs.hh"
#include "hb-meta.hh"

/* Unified iterator object.
 *
 * The goal of this template is to make the same iterator interface
 * available to all types, and make it very easy and compact to use.
 * hb_iter_tator objects are small, light-weight, objects that can be
 * copied by value.  If the collection / object being iterated on
 * is writable, then the iterator returns lvalues, otherwise it
 * returns rvalues.
 *
 * TODO Document more.
 *
 * If iterator implementation implements operator!=, then can be
 * used in range-based for loop.  That comes free if the iterator
 * is random-access.  Otherwise, the range-based for loop incurs
 * one traversal to find end(), which can be avoided if written
 * as a while-style for loop, or if iterator implements a faster
 * __end__() method.
 * TODO When opting in for C++17, address this by changing return
 * type of .end()?
 */

/*
 * Base classes for iterators.
 */

/* Base class for all iterators. */
template <typename iter_t, typename Item = typename iter_t::__item_t__>
struct hb_iter_t
{
  typedef Item item_t;
  constexpr unsigned get_item_size () const { return hb_static_size (Item); }
  static constexpr bool is_iterator = true;
  static constexpr bool is_random_access_iterator = false;
  static constexpr bool is_sorted_iterator = false;

  private:
  /* https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern */
  const iter_t* thiz () const { return static_cast<const iter_t *> (this); }
	iter_t* thiz ()       { return static_cast<      iter_t *> (this); }
  public:

  /* TODO:
   * Port operators below to use hb_enable_if to sniff which method implements
   * an operator and use it, and remove hb_iter_fallback_mixin_t completely. */

  /* Operators. */
  iter_t iter () const { return *thiz(); }
  iter_t operator + () const { return *thiz(); }
  iter_t begin () const { return *thiz(); }
  iter_t end () const { return thiz()->__end__ (); }
  explicit operator bool () const { return thiz()->__more__ (); }
  unsigned len () const { return thiz()->__len__ (); }
  /* The following can only be enabled if item_t is reference type.  Otherwise
   * it will be returning pointer to temporary rvalue.
   * TODO Use a wrapper return type to fix for non-reference type. */
  template <typename T = item_t,
	    hb_enable_if (hb_is_reference (T))>
  hb_remove_reference<item_t>* operator -> () const { return hb_addressof (**thiz()); }
  item_t operator * () const { return thiz()->__item__ (); }
  item_t operator * () { return thiz()->__item__ (); }
  item_t operator [] (unsigned i) const { return thiz()->__item_at__ (i); }
  item_t operator [] (unsigned i) { return thiz()->__item_at__ (i); }
  iter_t& operator += (unsigned count) &  { thiz()->__forward__ (count); return *thiz(); }
  iter_t  operator += (unsigned count) && { thiz()->__forward__ (count); return *thiz(); }
  iter_t& operator ++ () &  { thiz()->__next__ (); return *thiz(); }
  iter_t  operator ++ () && { thiz()->__next__ (); return *thiz(); }
  iter_t& operator -= (unsigned count) &  { thiz()->__rewind__ (count); return *thiz(); }
  iter_t  operator -= (unsigned count) && { thiz()->__rewind__ (count); return *thiz(); }
  iter_t& operator -- () &  { thiz()->__prev__ (); return *thiz(); }
  iter_t  operator -- () && { thiz()->__prev__ (); return *thiz(); }
  iter_t operator + (unsigned count) const { auto c = thiz()->iter (); c += count; return c; }
  friend iter_t operator + (unsigned count, const iter_t &it) { return it + count; }
  iter_t operator ++ (int) { iter_t c (*thiz()); ++*thiz(); return c; }
  iter_t operator - (unsigned count) const { auto c = thiz()->iter (); c -= count; return c; }
  iter_t operator -- (int) { iter_t c (*thiz()); --*thiz(); return c; }
  template <typename T>
  iter_t& operator >> (T &v) &  { v = **thiz(); ++*thiz(); return *thiz(); }
  template <typename T>
  iter_t  operator >> (T &v) && { v = **thiz(); ++*thiz(); return *thiz(); }
  template <typename T>
  iter_t& operator << (const T v) &  { **thiz() = v; ++*thiz(); return *thiz(); }
  template <typename T>
  iter_t  operator << (const T v) && { **thiz() = v; ++*thiz(); return *thiz(); }

  protected:
  hb_iter_t () = default;
  hb_iter_t (const hb_iter_t &o HB_UNUSED) = default;
  hb_iter_t (hb_iter_t &&o HB_UNUSED) = default;
  hb_iter_t& operator = (const hb_iter_t &o HB_UNUSED) = default;
  hb_iter_t& operator = (hb_iter_t &&o HB_UNUSED) = default;
};

#define HB_ITER_USING(Name) \
  using item_t = typename Name::item_t; \
  using Name::begin; \
  using Name::end; \
  using Name::get_item_size; \
  using Name::is_iterator; \
  using Name::iter; \
  using Name::operator bool; \
  using Name::len; \
  using Name::operator ->; \
  using Name::operator *; \
  using Name::operator []; \
  using Name::operator +=; \
  using Name::operator ++; \
  using Name::operator -=; \
  using Name::operator --; \
  using Name::operator +; \
  using Name::operator -; \
  using Name::operator >>; \
  using Name::operator <<; \
  static_assert (true, "")

/* Returns iterator / item type of a type. */
template <typename Iterable>
using hb_iter_type = decltype (hb_deref (hb_declval (Iterable)).iter ());
template <typename Iterable>
using hb_item_type = decltype (*hb_deref (hb_declval (Iterable)).iter ());

template <typename> struct hb_array_t;
template <typename> struct hb_sorted_array_t;

struct
{
  template <typename T> hb_iter_type<T>
  operator () (T&& c) const
  { return hb_deref (hb_forward<T> (c)).iter (); }

  /* Specialization for C arrays. */

  template <typename Type> inline hb_array_t<Type>
  operator () (Type *array, unsigned int length) const
  { return hb_array_t<Type> (array, length); }

  template <typename Type, unsigned int length> hb_array_t<Type>
  operator () (Type (&array)[length]) const
  { return hb_array_t<Type> (array, length); }

}
HB_FUNCOBJ (hb_iter);
struct
{
  template <typename T> unsigned
  operator () (T&& c) const
  { return c.len (); }

}
HB_FUNCOBJ (hb_len);

/* Mixin to fill in what the subclass doesn't provide. */
template <typename iter_t, typename item_t = typename iter_t::__item_t__>
struct hb_iter_fallback_mixin_t
{
  private:
  /* https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern */
  const iter_t* thiz () const { return static_cast<const iter_t *> (this); }
	iter_t* thiz ()       { return static_cast<      iter_t *> (this); }
  public:

  /* Access: Implement __item__(), or __item_at__() if random-access. */
  item_t __item__ () const { return (*thiz())[0]; }
  item_t __item_at__ (unsigned i) const { return *(*thiz() + i); }

  /* Termination: Implement __more__(), or __len__() if random-access. */
  bool __more__ () const { return bool (thiz()->len ()); }
  unsigned __len__ () const
  { iter_t c (*thiz()); unsigned l = 0; while (c) { c++; l++; } return l; }

  /* Advancing: Implement __next__(), or __forward__() if random-access. */
  void __next__ () { *thiz() += 1; }
  void __forward__ (unsigned n) { while (*thiz() && n--) ++*thiz(); }

  /* Rewinding: Implement __prev__() or __rewind__() if bidirectional. */
  void __prev__ () { *thiz() -= 1; }
  void __rewind__ (unsigned n) { while (*thiz() && n--) --*thiz(); }

  /* Range-based for: Implement __end__() if can be done faster,
   * and operator!=. */
  iter_t __end__ () const
  {
    if (thiz()->is_random_access_iterator)
      return *thiz() + thiz()->len ();
    /* Above expression loops twice. Following loops once. */
    auto it = *thiz();
    while (it) ++it;
    return it;
  }

  protected:
  hb_iter_fallback_mixin_t () = default;
  hb_iter_fallback_mixin_t (const hb_iter_fallback_mixin_t &o HB_UNUSED) = default;
  hb_iter_fallback_mixin_t (hb_iter_fallback_mixin_t &&o HB_UNUSED) = default;
  hb_iter_fallback_mixin_t& operator = (const hb_iter_fallback_mixin_t &o HB_UNUSED) = default;
  hb_iter_fallback_mixin_t& operator = (hb_iter_fallback_mixin_t &&o HB_UNUSED) = default;
};

template <typename iter_t, typename item_t = typename iter_t::__item_t__>
struct hb_iter_with_fallback_t :
  hb_iter_t<iter_t, item_t>,
  hb_iter_fallback_mixin_t<iter_t, item_t>
{
  protected:
  hb_iter_with_fallback_t () = default;
  hb_iter_with_fallback_t (const hb_iter_with_fallback_t &o HB_UNUSED) = default;
  hb_iter_with_fallback_t (hb_iter_with_fallback_t &&o HB_UNUSED) = default;
  hb_iter_with_fallback_t& operator = (const hb_iter_with_fallback_t &o HB_UNUSED) = default;
  hb_iter_with_fallback_t& operator = (hb_iter_with_fallback_t &&o HB_UNUSED) = default;
};

/*
 * Meta-programming predicates.
 */

/* hb_is_iterator() / hb_is_iterator_of() */

template<typename Iter, typename Item>
struct hb_is_iterator_of
{
  template <typename Item2 = Item>
  static hb_true_type impl (hb_priority<2>, hb_iter_t<Iter, hb_type_identity<Item2>> *);
  static hb_false_type impl (hb_priority<0>, const void *);

  public:
  static constexpr bool value = decltype (impl (hb_prioritize, hb_declval (Iter*)))::value;
};
#define hb_is_iterator_of(Iter, Item) hb_is_iterator_of<Iter, Item>::value
#define hb_is_iterator(Iter) hb_is_iterator_of (Iter, typename Iter::item_t)

/* hb_is_iterable() */

template <typename T>
struct hb_is_iterable
{
  private:

  template <typename U>
  static auto impl (hb_priority<1>) -> decltype (hb_declval (U).iter (), hb_true_type ());

  template <typename>
  static hb_false_type impl (hb_priority<0>);

  public:
  static constexpr bool value = decltype (impl<T> (hb_prioritize))::value;
};
#define hb_is_iterable(Iterable) hb_is_iterable<Iterable>::value

/* hb_is_source_of() / hb_is_sink_of() */

template<typename Iter, typename Item>
struct hb_is_source_of
{
  private:
  template <typename Iter2 = Iter,
	    hb_enable_if (hb_is_convertible (typename Iter2::item_t, hb_add_lvalue_reference<hb_add_const<Item>>))>
  static hb_true_type impl (hb_priority<2>);
  template <typename Iter2 = Iter>
  static auto impl (hb_priority<1>) -> decltype (hb_declval (Iter2) >> hb_declval (Item &), hb_true_type ());
  static hb_false_type impl (hb_priority<0>);

  public:
  static constexpr bool value = decltype (impl (hb_prioritize))::value;
};
#define hb_is_source_of(Iter, Item) hb_is_source_of<Iter, Item>::value

template<typename Iter, typename Item>
struct hb_is_sink_of
{
  private:
  template <typename Iter2 = Iter,
	    hb_enable_if (hb_is_convertible (typename Iter2::item_t, hb_add_lvalue_reference<Item>))>
  static hb_true_type impl (hb_priority<2>);
  template <typename Iter2 = Iter>
  static auto impl (hb_priority<1>) -> decltype (hb_declval (Iter2) << hb_declval (Item), hb_true_type ());
  static hb_false_type impl (hb_priority<0>);

  public:
  static constexpr bool value = decltype (impl (hb_prioritize))::value;
};
#define hb_is_sink_of(Iter, Item) hb_is_sink_of<Iter, Item>::value

/* This is commonly used, so define: */
#define hb_is_sorted_source_of(Iter, Item) \
	(hb_is_source_of(Iter, Item) && Iter::is_sorted_iterator)

/* Range-based 'for' for iterables. */

template <typename Iterable,
	  hb_requires (hb_is_iterable (Iterable))>
static inline auto begin (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).begin ())

template <typename Iterable,
	  hb_requires (hb_is_iterable (Iterable))>
static inline auto end (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).end ())

/* begin()/end() are NOT looked up non-ADL.  So each namespace must declare them.
 * Do it for namespace OT. */
namespace OT {

template <typename Iterable,
	  hb_requires (hb_is_iterable (Iterable))>
static inline auto begin (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).begin ())

template <typename Iterable,
	  hb_requires (hb_is_iterable (Iterable))>
static inline auto end (Iterable&& iterable) HB_AUTO_RETURN (hb_iter (iterable).end ())

}

/*
 * Adaptors, combiners, etc.
 */

template <typename Lhs, typename Rhs,
	  hb_requires (hb_is_iterator (Lhs))>
static inline auto
operator | (Lhs&& lhs, Rhs&& rhs) HB_AUTO_RETURN (hb_forward<Rhs> (rhs) (hb_forward<Lhs> (lhs)))

/* hb_map(), hb_filter(), hb_reduce() */

enum  class hb_function_sortedness_t {
  NOT_SORTED,
  RETAINS_SORTING,
  SORTED,
};

template <typename Iter, typename Proj, hb_function_sortedness_t Sorted,
	 hb_requires (hb_is_iterator (Iter))>
struct hb_map_iter_t :
  hb_iter_t<hb_map_iter_t<Iter, Proj, Sorted>,
	    decltype (hb_get (hb_declval (Proj), *hb_declval (Iter)))>
{
  hb_map_iter_t (const Iter& it, Proj f_) : it (it), f (f_) {}

  typedef decltype (hb_get (hb_declval (Proj), *hb_declval (Iter))) __item_t__;
  static constexpr bool is_random_access_iterator = Iter::is_random_access_iterator;
  static constexpr bool is_sorted_iterator =
    Sorted == hb_function_sortedness_t::SORTED ? true :
    Sorted == hb_function_sortedness_t::RETAINS_SORTING ? Iter::is_sorted_iterator :
    false;
  __item_t__ __item__ () const { return hb_get (f.get (), *it); }
  __item_t__ __item_at__ (unsigned i) const { return hb_get (f.get (), it[i]); }
  bool __more__ () const { return bool (it); }
  unsigned __len__ () const { return it.len (); }
  void __next__ () { ++it; }
  void __forward__ (unsigned n) { it += n; }
  void __prev__ () { --it; }
  void __rewind__ (unsigned n) { it -= n; }
  hb_map_iter_t __end__ () const { return hb_map_iter_t (it.end (), f); }
  bool operator != (const hb_map_iter_t& o) const
  { return it != o.it; }

  private:
  Iter it;
  hb_reference_wrapper<Proj> f;
};

template <typename Proj, hb_function_sortedness_t Sorted>
struct hb_map_iter_factory_t
{
  hb_map_iter_factory_t (Proj f) : f (f) {}

  template <typename Iter,
	    hb_requires (hb_is_iterator (Iter))>
  hb_map_iter_t<Iter, Proj, Sorted>
  operator () (Iter it)
  { return hb_map_iter_t<Iter, Proj, Sorted> (it, f); }

  private:
  Proj f;
};
struct
{
  template <typename Proj>
  hb_map_iter_factory_t<Proj, hb_function_sortedness_t::NOT_SORTED>
  operator () (Proj&& f) const
  { return hb_map_iter_factory_t<Proj, hb_function_sortedness_t::NOT_SORTED> (f); }
}
HB_FUNCOBJ (hb_map);
struct
{
  template <typename Proj>
  hb_map_iter_factory_t<Proj, hb_function_sortedness_t::RETAINS_SORTING>
  operator () (Proj&& f) const
  { return hb_map_iter_factory_t<Proj, hb_function_sortedness_t::RETAINS_SORTING> (f); }
}
HB_FUNCOBJ (hb_map_retains_sorting);
struct
{
  template <typename Proj>
  hb_map_iter_factory_t<Proj, hb_function_sortedness_t::SORTED>
  operator () (Proj&& f) const
  { return hb_map_iter_factory_t<Proj, hb_function_sortedness_t::SORTED> (f); }
}
HB_FUNCOBJ (hb_map_sorted);

template <typename Iter, typename Pred, typename Proj,
	 hb_requires (hb_is_iterator (Iter))>
struct hb_filter_iter_t :
  hb_iter_with_fallback_t<hb_filter_iter_t<Iter, Pred, Proj>,
			  typename Iter::item_t>
{
  hb_filter_iter_t (const Iter& it_, Pred p_, Proj f_) : it (it_), p (p_), f (f_)
  { while (it && !hb_has (p.get (), hb_get (f.get (), *it))) ++it; }

  typedef typename Iter::item_t __item_t__;
  static constexpr bool is_sorted_iterator = Iter::is_sorted_iterator;
  __item_t__ __item__ () const { return *it; }
  bool __more__ () const { return bool (it); }
  void __next__ () { do ++it; while (it && !hb_has (p.get (), hb_get (f.get (), *it))); }
  void __prev__ () { do --it; while (it && !hb_has (p.get (), hb_get (f.get (), *it))); }
  hb_filter_iter_t __end__ () const { return hb_filter_iter_t (it.end (), p, f); }
  bool operator != (const hb_filter_iter_t& o) const
  { return it != o.it; }

  private:
  Iter it;
  hb_reference_wrapper<Pred> p;
  hb_reference_wrapper<Proj> f;
};
template <typename Pred, typename Proj>
struct hb_filter_iter_factory_t
{
  hb_filter_iter_factory_t (Pred p, Proj f) : p (p), f (f) {}

  template <typename Iter,
	    hb_requires (hb_is_iterator (Iter))>
  hb_filter_iter_t<Iter, Pred, Proj>
  operator () (Iter it)
  { return hb_filter_iter_t<Iter, Pred, Proj> (it, p, f); }

  private:
  Pred p;
  Proj f;
};
struct
{
  template <typename Pred = decltype ((hb_identity)),
	    typename Proj = decltype ((hb_identity))>
  hb_filter_iter_factory_t<Pred, Proj>
  operator () (Pred&& p = hb_identity, Proj&& f = hb_identity) const
  { return hb_filter_iter_factory_t<Pred, Proj> (p, f); }
}
HB_FUNCOBJ (hb_filter);

template <typename Redu, typename InitT>
struct hb_reduce_t
{
  hb_reduce_t (Redu r, InitT init_value) : r (r), init_value (init_value) {}

  template <typename Iter,
	    hb_requires (hb_is_iterator (Iter)),
	    typename AccuT = hb_decay<decltype (hb_declval (Redu) (hb_declval (InitT), hb_declval (typename Iter::item_t)))>>
  AccuT
  operator () (Iter it)
  {
    AccuT value = init_value;
    for (; it; ++it)
      value = r (value, *it);
    return value;
  }

  private:
  Redu r;
  InitT init_value;
};
struct
{
  template <typename Redu, typename InitT>
  hb_reduce_t<Redu, InitT>
  operator () (Redu&& r, InitT init_value) const
  { return hb_reduce_t<Redu, InitT> (r, init_value); }
}
HB_FUNCOBJ (hb_reduce);

/* hb_zip() */

template <typename A, typename B>
struct hb_zip_iter_t :
  hb_iter_t<hb_zip_iter_t<A, B>,
	    hb_pair_t<typename A::item_t, typename B::item_t>>
{
  hb_zip_iter_t () {}
  hb_zip_iter_t (const A& a, const B& b) : a (a), b (b) {}

  typedef hb_pair_t<typename A::item_t, typename B::item_t> __item_t__;
  static constexpr bool is_random_access_iterator =
    A::is_random_access_iterator &&
    B::is_random_access_iterator;
  /* Note.  The following categorization is only valid if A is strictly sorted,
   * ie. does NOT have duplicates.  Previously I tried to categorize sortedness
   * more granularly, see commits:
   *
   *   513762849a683914fc266a17ddf38f133cccf072
   *   4d3cf2adb669c345cc43832d11689271995e160a
   *
   * However, that was not enough, since hb_sorted_array_t, hb_sorted_vector_t,
   * SortedArrayOf, etc all needed to be updated to add more variants.  At that
   * point I saw it not worth the effort, and instead we now deem all sorted
   * collections as essentially strictly-sorted for the purposes of zip.
   *
   * The above assumption is not as bad as it sounds.  Our "sorted" comes with
   * no guarantees.  It's just a contract, put in place to help you remember,
   * and think about, whether an iterator you receive is expected to be
   * sorted or not.  As such, it's not perfect by definition, and should not
   * be treated so.  The inaccuracy here just errs in the direction of being
   * more permissive, so your code compiles instead of erring on the side of
   * marking your zipped iterator unsorted in which case your code won't
   * compile.
   *
   * This semantical limitation does NOT affect logic in any other place I
   * know of as of this writing.
   */
  static constexpr bool is_sorted_iterator = A::is_sorted_iterator;

  __item_t__ __item__ () const { return __item_t__ (*a, *b); }
  __item_t__ __item_at__ (unsigned i) const { return __item_t__ (a[i], b[i]); }
  bool __more__ () const { return bool (a) && bool (b); }
  unsigned __len__ () const { return hb_min (a.len (), b.len ()); }
  void __next__ () { ++a; ++b; }
  void __forward__ (unsigned n) { a += n; b += n; }
  void __prev__ () { --a; --b; }
  void __rewind__ (unsigned n) { a -= n; b -= n; }
  hb_zip_iter_t __end__ () const { return hb_zip_iter_t (a.end (), b.end ()); }
  /* Note, we should stop if ANY of the iters reaches end.  As such two compare
   * unequal if both items are unequal, NOT if either is unequal. */
  bool operator != (const hb_zip_iter_t& o) const
  { return a != o.a && b != o.b; }

  private:
  A a;
  B b;
};
struct
{ HB_PARTIALIZE(2);
  template <typename A, typename B,
	    hb_requires (hb_is_iterable (A) && hb_is_iterable (B))>
  hb_zip_iter_t<hb_iter_type<A>, hb_iter_type<B>>
  operator () (A&& a, B&& b) const
  { return hb_zip_iter_t<hb_iter_type<A>, hb_iter_type<B>> (hb_iter (a), hb_iter (b)); }
}
HB_FUNCOBJ (hb_zip);

/* hb_apply() */

template <typename Appl>
struct hb_apply_t
{
  hb_apply_t (Appl a) : a (a) {}

  template <typename Iter,
	    hb_requires (hb_is_iterator (Iter))>
  void operator () (Iter it)
  {
    for (; it; ++it)
      (void) hb_invoke (a, *it);
  }

  private:
  Appl a;
};
struct
{
  template <typename Appl> hb_apply_t<Appl>
  operator () (Appl&& a) const
  { return hb_apply_t<Appl> (a); }

  template <typename Appl> hb_apply_t<Appl&>
  operator () (Appl *a) const
  { return hb_apply_t<Appl&> (*a); }
}
HB_FUNCOBJ (hb_apply);

/* hb_range()/hb_iota()/hb_repeat() */

template <typename T, typename S>
struct hb_range_iter_t :
  hb_iter_t<hb_range_iter_t<T, S>, T>
{
  hb_range_iter_t (T start, T end_, S step) : v (start), end_ (end_for (start, end_, step)), step (step) {}

  typedef T __item_t__;
  static constexpr bool is_random_access_iterator = true;
  static constexpr bool is_sorted_iterator = true;
  __item_t__ __item__ () const { return hb_ridentity (v); }
  __item_t__ __item_at__ (unsigned j) const { return v + j * step; }
  bool __more__ () const { return v != end_; }
  unsigned __len__ () const { return !step ? UINT_MAX : (end_ - v) / step; }
  void __next__ () { v += step; }
  void __forward__ (unsigned n) { v += n * step; }
  void __prev__ () { v -= step; }
  void __rewind__ (unsigned n) { v -= n * step; }
  hb_range_iter_t __end__ () const { return hb_range_iter_t (end_, end_, step); }
  bool operator != (const hb_range_iter_t& o) const
  { return v != o.v; }

  private:
  static inline T end_for (T start, T end_, S step)
  {
    if (!step)
      return end_;
    auto res = (end_ - start) % step;
    if (!res)
      return end_;
    end_ += step - res;
    return end_;
  }

  private:
  T v;
  T end_;
  S step;
};
struct
{
  template <typename T = unsigned> hb_range_iter_t<T, unsigned>
  operator () (T end = (unsigned) -1) const
  { return hb_range_iter_t<T, unsigned> (0, end, 1u); }

  template <typename T, typename S = unsigned> hb_range_iter_t<T, S>
  operator () (T start, T end, S step = 1u) const
  { return hb_range_iter_t<T, S> (start, end, step); }
}
HB_FUNCOBJ (hb_range);

template <typename T, typename S>
struct hb_iota_iter_t :
  hb_iter_with_fallback_t<hb_iota_iter_t<T, S>, T>
{
  hb_iota_iter_t (T start, S step) : v (start), step (step) {}

  private:

  template <typename S2 = S>
  auto
  inc (hb_type_identity<S2> s, hb_priority<1>)
    -> hb_void_t<decltype (hb_invoke (hb_forward<S2> (s), hb_declval<T&> ()))>
  { v = hb_invoke (hb_forward<S2> (s), v); }

  void
  inc (S s, hb_priority<0>)
  { v += s; }

  public:

  typedef T __item_t__;
  static constexpr bool is_random_access_iterator = true;
  static constexpr bool is_sorted_iterator = true;
  __item_t__ __item__ () const { return hb_ridentity (v); }
  bool __more__ () const { return true; }
  unsigned __len__ () const { return UINT_MAX; }
  void __next__ () { inc (step, hb_prioritize); }
  void __prev__ () { v -= step; }
  hb_iota_iter_t __end__ () const { return *this; }
  bool operator != (const hb_iota_iter_t& o) const { return true; }

  private:
  T v;
  S step;
};
struct
{
  template <typename T = unsigned, typename S = unsigned> hb_iota_iter_t<T, S>
  operator () (T start = 0u, S step = 1u) const
  { return hb_iota_iter_t<T, S> (start, step); }
}
HB_FUNCOBJ (hb_iota);

template <typename T>
struct hb_repeat_iter_t :
  hb_iter_t<hb_repeat_iter_t<T>, T>
{
  hb_repeat_iter_t (T value) : v (value) {}

  typedef T __item_t__;
  static constexpr bool is_random_access_iterator = true;
  static constexpr bool is_sorted_iterator = true;
  __item_t__ __item__ () const { return v; }
  __item_t__ __item_at__ (unsigned j) const { return v; }
  bool __more__ () const { return true; }
  unsigned __len__ () const { return UINT_MAX; }
  void __next__ () {}
  void __forward__ (unsigned) {}
  void __prev__ () {}
  void __rewind__ (unsigned) {}
  hb_repeat_iter_t __end__ () const { return *this; }
  bool operator != (const hb_repeat_iter_t& o) const { return true; }

  private:
  T v;
};
struct
{
  template <typename T> hb_repeat_iter_t<T>
  operator () (T value) const
  { return hb_repeat_iter_t<T> (value); }
}
HB_FUNCOBJ (hb_repeat);

/* hb_enumerate()/hb_take() */

struct
{
  template <typename Iterable,
	    typename Index = unsigned,
	    hb_requires (hb_is_iterable (Iterable))>
  auto operator () (Iterable&& it, Index start = 0u) const HB_AUTO_RETURN
  ( hb_zip (hb_iota (start), it) )
}
HB_FUNCOBJ (hb_enumerate);

struct
{ HB_PARTIALIZE(2);
  template <typename Iterable,
	    hb_requires (hb_is_iterable (Iterable))>
  auto operator () (Iterable&& it, unsigned count) const HB_AUTO_RETURN
  ( hb_zip (hb_range (count), it) | hb_map (hb_second) )

  /* Specialization arrays. */

  template <typename Type> inline hb_array_t<Type>
  operator () (hb_array_t<Type> array, unsigned count) const
  { return array.sub_array (0, count); }

  template <typename Type> inline hb_sorted_array_t<Type>
  operator () (hb_sorted_array_t<Type> array, unsigned count) const
  { return array.sub_array (0, count); }
}
HB_FUNCOBJ (hb_take);

struct
{ HB_PARTIALIZE(2);
  template <typename Iter,
	    hb_requires (hb_is_iterator (Iter))>
  auto operator () (Iter it, unsigned count) const HB_AUTO_RETURN
  (
    + hb_iota (it, hb_add (count))
    | hb_map (hb_take (count))
    | hb_take ((hb_len (it) + count - 1) / count)
  )
}
HB_FUNCOBJ (hb_chop);

/* hb_sink() */

template <typename Sink>
struct hb_sink_t
{
  hb_sink_t (Sink s) : s (s) {}

  template <typename Iter,
	    hb_requires (hb_is_iterator (Iter))>
  void operator () (Iter it)
  {
    for (; it; ++it)
      s << *it;
  }

  private:
  Sink s;
};
struct
{
  template <typename Sink> hb_sink_t<Sink>
  operator () (Sink&& s) const
  { return hb_sink_t<Sink> (s); }

  template <typename Sink> hb_sink_t<Sink&>
  operator () (Sink *s) const
  { return hb_sink_t<Sink&> (*s); }
}
HB_FUNCOBJ (hb_sink);

/* hb-drain: hb_sink to void / blackhole / /dev/null. */

struct
{
  template <typename Iter,
	    hb_requires (hb_is_iterator (Iter))>
  void operator () (Iter it) const
  {
    for (; it; ++it)
      (void) *it;
  }
}
HB_FUNCOBJ (hb_drain);

/* hb_unzip(): unzip and sink to two sinks. */

template <typename Sink1, typename Sink2>
struct hb_unzip_t
{
  hb_unzip_t (Sink1 s1, Sink2 s2) : s1 (s1), s2 (s2) {}

  template <typename Iter,
	    hb_requires (hb_is_iterator (Iter))>
  void operator () (Iter it)
  {
    for (; it; ++it)
    {
      const auto &v = *it;
      s1 << v.first;
      s2 << v.second;
    }
  }

  private:
  Sink1 s1;
  Sink2 s2;
};
struct
{
  template <typename Sink1, typename Sink2> hb_unzip_t<Sink1, Sink2>
  operator () (Sink1&& s1, Sink2&& s2) const
  { return hb_unzip_t<Sink1, Sink2> (s1, s2); }

  template <typename Sink1, typename Sink2> hb_unzip_t<Sink1&, Sink2&>
  operator () (Sink1 *s1, Sink2 *s2) const
  { return hb_unzip_t<Sink1&, Sink2&> (*s1, *s2); }
}
HB_FUNCOBJ (hb_unzip);

/* hb-all, hb-any, hb-none. */

struct
{
  template <typename Iterable,
	    typename Pred = decltype ((hb_identity)),
	    typename Proj = decltype ((hb_identity)),
	    hb_requires (hb_is_iterable (Iterable))>
  bool operator () (Iterable&& c,
		    Pred&& p = hb_identity,
		    Proj&& f = hb_identity) const
  {
    for (auto it = hb_iter (c); it; ++it)
      if (!hb_match (hb_forward<Pred> (p), hb_get (hb_forward<Proj> (f), *it)))
	return false;
    return true;
  }
}
HB_FUNCOBJ (hb_all);
struct
{
  template <typename Iterable,
	    typename Pred = decltype ((hb_identity)),
	    typename Proj = decltype ((hb_identity)),
	    hb_requires (hb_is_iterable (Iterable))>
  bool operator () (Iterable&& c,
		    Pred&& p = hb_identity,
		    Proj&& f = hb_identity) const
  {
    for (auto it = hb_iter (c); it; ++it)
      if (hb_match (hb_forward<Pred> (p), hb_get (hb_forward<Proj> (f), *it)))
	return true;
    return false;
  }
}
HB_FUNCOBJ (hb_any);
struct
{
  template <typename Iterable,
	    typename Pred = decltype ((hb_identity)),
	    typename Proj = decltype ((hb_identity)),
	    hb_requires (hb_is_iterable (Iterable))>
  bool operator () (Iterable&& c,
		    Pred&& p = hb_identity,
		    Proj&& f = hb_identity) const
  {
    for (auto it = hb_iter (c); it; ++it)
      if (hb_match (hb_forward<Pred> (p), hb_get (hb_forward<Proj> (f), *it)))
	return false;
    return true;
  }
}
HB_FUNCOBJ (hb_none);

/*
 * Algorithms operating on iterators.
 */

template <typename C, typename V,
	  hb_requires (hb_is_iterable (C))>
inline void
hb_fill (C& c, const V &v)
{
  for (auto i = hb_iter (c); i; i++)
    *i = v;
}

template <typename S, typename D>
inline void
hb_copy (S&& is, D&& id)
{
  hb_iter (is) | hb_sink (id);
}

#endif /* HB_ITER_HH */